Teorija grafova

Uvod i motivacija

Teorija grafova je grana diskretne matematike koja se bavi proučavanjem grafova. Grafovi su nam korisni jer se prirodno pojavljuju u raznim kombinatornim problemima u kojima su elementi povezani na određen način ili u problemima optimizacije, primjerice pri traženju najkraćeg puta u sustavima za navigaciju. Prije nego što formaliziramo što je zapravo graf, kakvi grafovi postoje i navedemo još neke od problema koje rješavamo promatrajući grafove koji modeliraju zadane probleme, spomenut ćemo problem königsberških mostova, značajan za razvoj teorije grafova kao zasebne grane matematike.

Königsberški mostovi

Ovaj problem iz stvarnog svijeta postavio je poznati švicarski matematičar Leonhard Euler, potaknut rasporedom sedam mostova grada Königsberga (današnjeg Kalinjingrada) Grad je je ležao s obje strane rijeke Pregel koja ga je razdijelila na “kopno” i dva otoka, kao što se vidi gore na naslovnoj slici i na slici 1.

Cilj je bio utvrditi postoji li šetnja gradom takva da se svaki most prijeđe samo jednom, a u slučaju potvrdnog odgovora trebalo je konstruirati takvu šetnju. Na ovaj ćemo se problem vratiti u nastavku.

Osnovni pojmovi i definicije

Graf je uređeni par skupa vrhova $V$ i skupa bridova $E$, pri čemu je svaki brid $e\in E$ oblika $\{v_1, v_2\}$, gdje su $v_1, v_2 \in V$.

Ovu definiciju grafa s neusmjerenim bridovima nekada mijenjamo na način da dozvoljavamo usmjerene bridove (tada je $E$ skup uređenih parova iz $V$), petlje (koje vrhove povezuju same sa sobom) te višestruke bridove. Graf s neusmjerenim, jednostrukim bridovima bez petlji zovemo jednostavni graf, onaj s usmjerenim bridovima zovemo digraf i konačno onaj s višestukim bridovima, multigraf. Graf u kojem su svaka dva vrha međusobno povezana zvat ćemo potpunim, a onaj u kojem nijedan par vrhova nije povezan praznim grafom.

Vratimo se na primjer königsberških mostova i prikažimo taj problem grafom. Naime, bitno je primijetiti da iako mostovi nemaju iste fizičke završne točke na nekom dijelu kopna, njih prikazujemo istom točkom jer se od jedne do druge takve točke dolazi ne koristeći se mostom, pa ih nemamo potrebu razlikovati jer to ne utječe na promatrani problem.

Ovaj je problem zapravo ekvivalentan ispitivanju mogućnosti crtanja lika (grafa) sa slike jednim potezom olovke, odnosno bez dizanja olovke i bez ponovnog prelaženja već nacrtanih linija. Ti uvjeti osiguravaju da se linijama nacrtanima jednim potezom olovke može proći stazom (bez ikakvih preskakanja s jednog mjesta na drugo i bez ponavljanja bridova).

Za dva ćemo vrha $v, t \in V$ reći da su susjedni ako postoji brid $\{v, t\} \in E$. Za vrh $v \in V$ i brid $e \in E$ reći ćemo da su incidentni ako postoji vrh $u \in V$ takav da je $e=\{v, u\}$. Stupanj vrha $v \in V$ definiramo kao broj bridova incidentnih s vrhom $v$ i označavamo ga s $d(v)$. Vrh stupnja $0$ zovemo izoliranim vrhom. Na primjer, stupanj vrha $A$ u grafu na slici 2 je pet.

Teorem 1. (Lema o rukovanju)
Zbroj stupnjeva vrhova $\sum_{v \in V}d(v)$ u proizvoljnom je grafu paran broj.

Dokaz.
Svaki brid grafa povezuje dva njegova vrha pa tako pridonosi zbroju svih stupnjeva s dva. Zato je ukupan zbroj stupnjeva vrhova u grafu jednak dvostrukom broju bridova tog grafa, odnosno paran je broj.

$Q.E.D.$

Kako bismo malo provježbali intuiciju oko novonaučenih pojmova, promotrimo idući zadatak.

Zadatak (Materijali za pripremu – Matematička natjecanja – Teorija grafova).
Neka je $S$ skup koji se sastoji od $m$ parova $(a, b)$ prirodnih brojeva takvih da $1 \leq a < b \leq n$. Dokaži da postoji barem $\frac{4m}{3n}\left(m-\frac{n^2}{4}\right)$ trojki $(a, b, c)$ takvih da $(a, b), (b, c), (a, c) \in S$.

Rješenje.
Graf $G$ definirat ćemo na način da mu je skup vrhova $V=\{1, 2, \ldots, n\}$, a dva su vrha $a$ i $b$ susjedna ako je $(a, b) \in S$ ili $(b, a)\in S$. Reći ćemo da je trojka vrhova $\{a, b, c\}$ trokut ako vrijedi $(a, b), (b, c), (a, c) \in S$. Dakle, zadatak je naći donju granicu za broj trokuta koji ćemo označiti s $K$.

Za susjedne vrhove $x, y$, neka je $k$ broj vrhova susjednih $x$ i $y$, a $l$ broj vrhova susjednih $x$ ili $y$ ne uključujući njih same. Primijetimo da $k$ također predstavlja broj trokuta u kojima se nalaze $x$ i $y$. Tada po formuli uključivanja i isključivanja primijenjenoj na skupove svih vrhova iz $V \setminus \{x, y\}$ koji su susjedni vrhu $x$, odnosno vrhu $y$ znamo da vrijedi $d(x)-1+d(y)-1-k=l \leq n-2$, pa vrijedi $k \geq d(x)+d(y)-n$. Ukupan broj trokuta $K$ je tada barem $\frac 1 3 \sum_{(x, y) \in S}{(d(x)+d(y)-n)}$, pri čemu dijelimo s tri jer smo u ovakvom zbrajanju svaki trokut pribrojili tri puta.

Primijetimo da vrijedi $$\sum_{(x, y) \in S}{(d(x)+d(y))}=\sum_{i=1}^n{d(i)^2}.$$
Izraz $(d(x)+d(y))$ na lijevoj strani jednakosti zbrajamo po svim susjednim vrhovima $(x,y)$ pa će se za svaki vrh $x$ vrijednost $d(x)$ pribrojiti točno $d(x)$ puta, jednom za svaki vrh koji je susjedan vrhu $x$. Dakle, ukupan zbroj možemo dobiti i zbrajanjem vrijednosti $d(i)^2$ za svaki vrh $i\in V$. Koristeći se veličinom skupa $S$ i dokazanom jednakosti, imamo
\begin{align} K &\geq \frac 1 3 \sum_{(x, y) \in S}{(d(x)+d(y)-n)} \\
&= \frac 1 3 \sum_{(x, y) \in S}{(d(x)+d(y))}-\frac{mn}3\\
&=\frac 1 3 \sum_{i=1}^n{d(i)^2}-\frac{mn}3. \end{align}

Iz A-K nejednakosti znamo da vrijedi $\sum_{i=1}^n{d(i)^2} \geq \frac 1 n (\sum_{i=1}^n{d(i)})^2= \frac 1 n (2m)^2$, pri čemu smo u zadnjem koraku iskoristili lemu o rukovanju. Konačno, vrijedi $$K \geq \frac {4m^2} {3n} – \frac {mn} 3= \frac{4m}{3n}\left(m-\frac{n^2}{4}\right).$$

$Q.E.D.$

Šetnje i povezanost

Definirat ćemo šetnju kao niz $(v_0, e_1, v_1,\ldots, v_{n-1}, e_n, v_n)$, za $v_i \in V$, $e_i \in E$ te ćemo reći da je ona zatvorena ako vrijedi $v_0=v_n$. Šetnju nerijetko prikazujemo navodeći samo bridove ili samo vrhove, no treba paziti da to radimo samo onda kada ne može doći do zabune radi višestrukih bridova. Nadalje, šetnju bez ponavljajućih bridova zvat ćemo stazom, a šetnju bez ponavljajućih vrhova putom. Zatvorenu stazu nazivamo ciklus. Duljinu šetnje definirat ćemo kao broj bridova u njoj.

Ekvivalentno je postojanje šetnje, staze i puta između dva vrha.

Za graf $G$ reći ćemo da je povezan ako za proizvoljna dva vrha postoji šetnja između njih. U suprotnom ćemo reći da je graf nepovezan i u tom ga slučaju možemo razdijeliti na komponente povezanosti.

Na primjer, lijevi graf sa slike 3 je povezan, a desni nepovezan i sastoji se od dviju komponenti povezanosti.

Teorem 2.
Neka je $n \geq 3$ prirodan broj. U jednostavnom grafu $G$ s $n$ vrhova i barem $n$ bridova postoji ciklus.

Dokaz.
Bez smanjenja općenitosti možemo pretpostaviti da je graf povezan. Naime, ako nije, promatrali bismo jednu od njegovih komponenti povezanosti za koju vrijedi pretpostavka da je broj bridova veći ili jednak broju vrhova i da je taj broj vrhova veći ili jednak tri. Zbog pretpostavke o $n$ vrhova i barem $n$ bridova, po Dirichletovu principu slijedi da barem jedna komponenta povezanosti mora imati broj bridova veći ili jednak broju vrhova. U jednostavnom grafu nema petlji, pa ne može biti samo jedan vrh; a nema ni višestrukih bridova pa ne mogu biti niti dva vrha, stoga takva komponenta povezanosti mora imati barem tri vrha. Dakle, komponenta povezanosti iz pretpostavke mora postojati.

Dokaz teorema provest ćemo indukcijom. Baza, $n=3$, jest ispunjena. Naime, jednostavan graf s tri vrha može imati najviše tri brida i u tom su slučaju svaka dva vrha povezana bridom.

Pretpostavimo da za neki $m \in \mathbb{N}, m\geq 3$ u proizvoljnom grafu s $m$ vrhova i barem $m$ bridova postoji ciklus. Uzmimo graf sa $m+1$ vrhom i barem $m+1$ bridova te razdvojimo na slučajeve kada on ima vrh stupnja $1$ i kada ga nema. Ako takav vrh postoji, primijetimo da njegovim uklanjanjem i uklanjanjem njemu incidentnog brida dobijemo graf na koji možemo primijeniti pretpostavku indukcije. Ako takav vrh ne postoji, slijedi da je svaki vrh stupnja barem $2$. Tada započnimo šetnju od proizvoljnog vrha $v$ (u jednom od dva smjera, nebitno kojem). Kako smo pretpostavili da je graf povezan, slijedi da, krenuvši od $v$ možemo doći do proizvoljnog vrha grafa, od kojeg opet možemo doći do proizvoljnog vrha grafa pa ovakvom šetnjom možemo doći do svakog od $m+1$ vrhova. Ako se u ovoj šetnji ijedan vrh $v$ pojavio dvaput, našli smo ciklus, kao šetnju između tih dvaju ponavljanja vrha $v$. Ako nije, prošetali smo $m+1$ vrhovima i $m$ bridovima koji ih povezuju. Tada znamo da nam je nužno ostao neki neiskorišten brid grafa čijim ćemo korištenjem spojiti dva vrha grafa koji su također bili povezani i nekim dijelom šetnje, čime smo dobili ciklus.

$Q.E.D.$

Još neke vrste grafova

Stazu koja prolazi svim bridovima grafa točno jednom zovemo Eulerova staza, a ako je ona k tome i zatvorena, nazivamo ju Eulerova tura. Primijetimo, u problemu königsberških mostova tražimo Eulerovu stazu odgovarajućeg grafa.

Za graf ćemo reći da je:

• bipartitan ako se skup vrhova može razdijeliti u dva podskupa $A, B$ takve da svaki brid povezuje jedan vrh iz $A$ i jedan vrh iz $B$

• Eulerov ako u njemu postoji Eulerova tura.

Teorem 3.

1. Jednostavan graf s $n$ vrhova je povezan ako ima više od ${n-1}\choose 2$ bridova.
2. Graf je bipartitan ako i samo ako nema ciklusa neparne duljine.
3. Multigraf bez izoliranih vrhova ima nezatvorenu Eulerovu stazu ako i samo ako je povezan i ima točno dva vrha neparnog stupnja.
4. Multigraf bez izoliranih vrhova je Eulerov ako i samo ako je povezan i svi su mu vrhovi parnog stupnja.

Dokaz.
Dokaz prve tvrdnje može se naći u skripti s predavanja iz kolegija Diskretna matematika.

Za dokaz jedne implikacije druge tvrdnje pretpostavimo da je graf bipartitan, odnosno da postoje $A$ i $B$ iz definicije bipartitnog grafa. Pretpostavimo da postoji ciklus neparne duljine, to jest, s neparnim brojem bridova, $(v_0, e_1, v_1, \ldots, e_k, v_k)$ za $k$ neparan broj i $v_0=v_k$. Bez smanjenja općenitosti možemo pretpostaviti $v_o \in A$ iz čega slijedi $v_1 \in B$, $v_2 \in A$, …, $v_k \in B$, što je u kontradikciji s $v_0=v_k$.

Obratno, neka graf nema neparnih ciklusa. Bez smanjenja općenitosti možemo pretpostaviti da je graf povezan (inače bismo isti dokaz proveli za svaku komponentu povezanosti grafa). Konstruirat ćemo skupove $A$ i $B$ iz definicije. Uzmimo neki $v \in V$ i stavimo $A =\{v\}, B= \emptyset$. Naizmjence ćemo stavljati u skup $B$ susjede elemenata iz $A$, a u skup $A$ susjede elemenata iz $B$ sve dok $A \cup B \neq V$.

Pokažimo da je gore opisan algoritam dobro definiran. Prvo, kako je graf povezan i konačan, algoritam će se u nekom trenutku zaustaviti. Pretpostavimo da postoji $w \in V$ takav da je $w \in A$ i $w \in B$. To znači da imamo šetnju neparne duljine (nije nužno put jer je moguće da ćemo se nekoliko puta vraćati u neke vrhove u ovom postupku) koja počinje i završava u $w$, ali u svakom ćemo slučaju od $v$ nakon “prelaska” parno mnogo bridova doći do $w$, i staviti $w$ u $A$, ali ćemo do $w$ doći i nakon “prelaska” neparno mnogo bridova, te staviti $w$ u $B$. Ono što smo dobili jesu šetnje parne i neparne duljine od $v$ do $w$. Njihovim spajanjem, za slučaj da nema ponavljanja međuvrhova, dobili smo neparan ciklus od $v$ do $w$. U slučaju ponavljanja međuvrhova, moguće je dobiti više manjih ciklusa, od kojih jedan sigurno mora biti neparne duljine, što je u kontradikciji s pretpostavkom.

Dokažimo sada treću i četvrtu tvrdnju. Time ćemo konačno utvrditi da ne postoji Eulerova staza za graf königsberških mostova, to jest ne postoji šetnja koja prolazi svakim mostom točno jednom.

Prvo ćemo dokazati nužnost uvjeta povezanosti i parnosti svih stupnjeva vrhova do na njih točno dva kada dokazujemo tvrdnju za nezatvorenu Eulerovu stazu. Nužnost povezanosti je očita pa se fokusirajmo na drugi uvjet.

Krećući se Eulerovom stazom, u svaki vrh staze ulazimo jednim bridom, a izlazimo drugim, tako da svakim prolaskom jednim takvim vrhom prolazimo njegovim bridovima u paru, pa je stupanj tih vrhova paran.

U nezatvorenoj Eulerovoj stazi stupnjevi prvog i zadnjeg vrha su neparni (iz njih smo jednom izašli na početku staze i jednom ušli na kraju staze). Primijetimo da ti stupnjevi nisu nužno $1$ jer smo se u te vrhove mogli proizvoljno puta vratiti tijekom staze, ali smo u njih trebali ući jednim, a izaći drugim bridom, pa to ne mijenja parnost njihovih stupnjeva.

Obratno, konstruktivno ćemo dokazati da su ti uvjeti (na povezanost i parnost stupnjeva svih do na točno dva vrha) dovoljni kako bismo zaključili da je multigraf bez izoliranih vrhova Eulerov, a u drugom slučaju ima nezatvorenu Eulerovu stazu.

Za dokaz četvrte tvrdnje uzet ćemo proizvoljan vrh $v$. Krenuvši iz vrha $v$, promotrit ćemo proizvoljnu stazu, dakle ne prelazeći dvaput bridovima kojima smo već prošli dokle god je to moguće. Skup $S$ definirat ćemo kao skup bridova te staze.

Primijetimo da staza mora završiti u početnom vrhu jer kada staza dođe do proizvoljnog vrha (različitog od $v)$ jednim njegovim incidentnim bridom, postojat će još neparan broj bridova (dakle strogo više od $0$) incidentnih s tim vrhom. Dakle, ne možemo “zaglaviti” u nekom takvom vrhu.

Ako sada vrijedi da je $S=E$, gotovi smo. U suprotnom postoji vrh $t$ koji je incidentan nekom bridu iz $S$, kao i nekom bridu iz $E \setminus S$, inače graf ne bi bio povezan. Nastavimo, u grafu $(V, E \setminus S)$ svaki je vrh opet parnog stupnja jer smo u našoj stazi prolazeći vrhove parnog stupnja iskoristili parno mnogo njima incidentnih bridova pa u $S \setminus E$ također preostaje parno mnogo njima incidentnih bridova. Dakle, krenemo li iz vrha $t$, koristeći se samo bridovima iz $E \setminus S$, možemo naći zatvorenu stazu na isti način kako smo to napravili i gore. Ove staze spajamo na način da krenemo iz $v$ i pratimo prvu stazu sve dok bridovima iz $S$ ne dođemo do $t$. Tada pratimo drugu stazu, bridovima iz $E \setminus S$, sve dok se ne vratimo u $t$, kada nastavimo prvom stazom do kraja. Ponavljanjem ovog postupka konačno mnogo puta dolazimo do tražene staze.

Dokaz treće tvrdnje teorema sličan je prethodnom pa ga nećemo prolaziti u cijelosti, već samo napomenuti razlike. Prvu stazu u trećoj tvrdnji (krećemo iz jednog od dvaju vrhova neparnog stupnja i isto kao gore) ne prelazimo niti jedan brid više nego jednom, dokle god je to moguće. Tvrdimo da će staza nužno završiti u drugom vrhu neparnog stupnja. Naime, jasno je kao i prije da staza ne može “zaglaviti” u vrhu parnog stupnja, ali trebamo opravdati i da neće zaglaviti u početnom vrhu. Za njega smo na samom početku staze iskoristili jedan njemu incidentan brid (kako bismo iz njega izašli) i u ostatku staze ga možemo poistovjetiti s vrhovima parnog stupnja, dakle i iz njega ćemo uvijek moći izaći. Nastavak dokaza isti je kao za četvrtu tvrdnju.

$Q.E.D.$

Kako su za graf iz problema königsberških mostova sva četiri vrha neparnog stupnja, zaključujemo da ne postoji Eulerova staza za taj graf. Ekvivalentno, iz ranijeg komentara znamo da taj graf ne bismo mogli nacrtati jednim potezom olovke, bez ponovnog prelaženja već nacrtanih bridova.

Za one koji žele znati više:

Definicija.
Sparivanje u grafu $G=(V, E)$ je podskup bridova $S \subseteq E$ takav da je svaki vrh incidentan najviše s jednim bridom iz $S$. Vrhove incidentne s bridom iz $S$ zovemo zasićenim, a u suprotnom nezasićenim}. Sparivanje koje zasićuje sve vrhove zovemo savršenim sparivanjem.

Teorem 4. (Hallov poučak o sparivanju).
Neka je $G$ bipartitan graf s biparticijom $V = X \cup Y$ . Za skup vrhova $A \subseteq X$ označimo s $N(A)$ skup svih vrhova susjednih nekom vrhu iz $A$. Graf $G$ dopušta sparivanje koje zasićuje sve vrhove iz $X$ ako i samo ako vrijedi uvjet $$|N(A)| \geq |A|\ \text{za svaki}\ A \subseteq X.$$

Dokaz Hallova poučka o sparivanju može se pronaći u skripti s predavanja za kolegij Kombinatorika.

Objasnimo teorem na primjeru. Zamislimo da u nekoj trgovini djevojke biraju haljine za maturalni ples. Djevojke ćemo reprezentirati kao vrhove iz skupa particije $X$, a haljine kao vrhove iz skupa particije $Y$. Recimo da postoji veza između djevojke i haljine ako bi djevojka bila sretna kad bi danu haljinu nosila na ples. Tada postoji sparivanje nad skupom djevojaka koje bi omogućilo da sve one budu sretne ako i samo ako za svaku grupu djevojaka, broj njihovih “zadovoljavajućih” haljina premašuje broj djevojaka u toj grupi.

Zadatci

Zadatak 1. (Državno natjecanje 2011, SŠ1A, 5.)
Supružnici Ana i Tomislav došli su na zabavu na kojoj su sudjelovala još četiri para. Prilikom dolaska dogodio se izvjestan broj rukovanja. Pritom se nitko nije rukovao sa svojim bračnim drugom niti sa samim sobom. Kada je kasnije Tomislav upitao sve prisutne s koliko su se osoba rukovali, dobio je devet različitih odgovora. S koliko se osoba rukovala Ana?

Uputa:
Ako se svatko mogao rukovati s najviše $8$, a najmanje $0$ ljudi, i svih $9$ ljudi koje je Tomislav pitao je ponudio drukčiji odgovor, jasno je da su ponuđeni odgovori bili $0, 1, …, 8$ rukovanja po osobi. S kime je nužno u braku osoba s $8$ rukovanja?

Rješenje:
Brzo se vidi da je osoba s osam rukovanja nužno u braku s osobom s niti jednim rukovanjem, naime, u suprotnom, osoba s osam rukovanja ne bi se rukovala sa sobom, svojim supružnikom i dodatno s osobom s niti jednim rukovanjem, pa ne bi mogla imati više od $10-1-1-1=7$ rukovanja. Slično nastavljamo, osoba koja se rukovala sa samo jednom osobom nužno se morala rukovati s osobom s osam rukovanja, pa ona mora biti u braku s osobom sa sedam rukovanja, inače se ta osoba ne bi rukovala sama sa sobom, svojim supružnikom, osobom niti s jednim i konačno, osobom s jednim rukovanjem po pretpostavci, no tada oni ne bi mogli imati više od $10-1-1-1-1=6$ rukovanja. Ovim postupkom zaključujemo da su u braku i osobe sa šest i dva te osobe s pet i tri rukovanja. Na kraju, ostaje samo jedna osoba, ona koja u ovom skupu nema svog supružnika i ona sa četiri rukovanja, a to je Ana.

Zadatak 2. (Materijali za pripremu – Matematička natjecanja – Teorija grafova)
Iz svakog vrha konveksnog poliedra izlaze $4$ brida. Dokaži da svaka ravnina koja ne prolazi niti jednim vrhom poliedra, siječe poliedar po mnogokutu s parnim brojem vrhova.

Uputa:
Primijenite lemu o rukovanju na bilo koji od nastalih poliedara (shvaćen kao graf).

Rješenje:
Ravnina siječe dani poliedar u dva nova. Nazovimo jednog od njih $P$. Neka je $m$ broj vrhova mnogokuta nastalog presjekom, a $n$ broj vrhova iz $P$ koji su uz to i iz početnog poliedra. Sada promatramo zbroj stupnjeva vrhova od $P$. Znamo da je svaki od $n$ starih vrhova stupnja $4$, a svaki od novih stupnja $3$. Tada je zbroj stupnjeva vrhova od $P$ jednak $4n+3m$, a kako to po lemi o rukovanju treba biti paran broj, zaključujemo da je $m$ paran.

Zadatak 3. (Materijali za pripremu – Matematička natjecanja – Teorija grafova, malo prilagođen zadatak)
Tijekom jednog školskog dana svaki od pet učenika zaspao je tijekom točno dva odmora. Svaka dva su u nekom trenutku spavala istovremeno (pretpostavljamo da su spavali cijeli odmor). Dokaži da je u nekom trenutku barem troje učenika spavalo istovremeno.

Uputa:
Za vrhove grafa uzmite uređeni par $(o, u)$ pri čemu nam je $o$ oznaka odmora, a $u$ učenika, ako je učenik $u$ spavao za vrijeme odmora $o$.

Rješenje:
Ovaj graf tada ima deset vrhova, po dva za svakog učenika. Dva vrha $(o_1, u_1), (o_2, u_2)$ povezat ćemo ako vrijedi $o_1=o_2$, to jest, ako je to spavanje učenika $u_1, u_2$ bilo pod istim odmorom. Po pretpostavci je svaki par spavao istovremeno u nekom trenutku, što će reći da svakog učenika spajamo (iz jednog ili drugog njemu pridruženog vrha, nije bitno kojeg) s preostalih četvero učenika (točnije, s jednim od dva njemu pridružena vrha). To radimo za petero učenika, ali primijetimo da bismo tako brid za istovremeno spavanje učenika $u_1, u_2$ povukli kad bismo postupak provodili za učenika $u_1$, ali i za učenika $u_2$, pa je zato ukupan broj bridova $\frac{4 \cdot 5}2=10$. Primjenom teorema 2. znamo da u ovakvom grafu postoji ciklus (duljine barem tri), odnosno da je barem troje učenika spavalo pod istim odmorom.

Zadatak 4. (Zadatak s interneta, poveznica na kraju)
Špil od $52$ karte dijelimo u $13$ skupina, svaka od po četiri karte. Dokaži da uvijek možemo izabrati po jednu kartu iz svake skupine tako da dobijemo svih $13$ vrijednosti karata.

Uputa:
Primijenite Hallov poučak o sparivanju na graf čiji su vrhovi particionirani u $X$, skup vrijednosti karte: as, dvojka, …, kralj i $Y$, skupine karata.

Rješenje:
Bridove između vrha skupine $y \in Y$ i vrha vrijednosti $x \in X$ povlačimo ako u zadanoj skupini $y$ postoji karta s vrijednosti $x$. Pretpostavimo suprotno, to jest da postoji $S \subset X$ takav da $|N(S)| < |S|$, to jest, za neki podskup $S$ od $k$ različitih vrijednosti karata, broj skupina u kojima su one sadržane je strogo manji od $k$. No to bi značilo da je količina od $4k$ karata (karte čija je vrijednost iz skupa $S$), sadržana u strogo manje od $4k$ karata (broj skupina je strogo manji od $k$).

Zadatak 5. (Državno natjecanje 2018, SŠ4A, 5. zadatak)
Na natjecanju sudjeluje $300$ natjecatelja. Svaka se dva natjecatelja međusobno ili poznaju ili ne poznaju, a ne postoje tri natjecatelja koji se svi međusobno poznaju. Odredi najveću moguću vrijednost broja $n$ tako da vrijede sljedeći uvjeti:

• Svaki natjecatelj poznaje najviše $n$ ostalih natjecatelja.
• Za svaki prirodni broj $m$ takav da je $1 \leq m \leq n$ postoji barem jedan natjecatelj koji poznaje točno $m$ ostalih natjecatelja.

Uputa:
Može li $n$ biti 201?

Rješenje:
Prvo ćemo ponuditi intuiciju iza upute:
Krenite sa što većim brojem mogućim, na primjer $299$. Tada za svaki $m$ prirodan broj, $m \leq 299$ mora postojati natjecatelj koji poznaje $m$ ljudi, posebno postoje natjecatelji koji poznaju redom $299$ i $298$ osoba. No, jasno je da se oni međusobno ne mogu poznavati jer bi po Dirichletovu principu poznavali zajedničku osobu, što je u kontradikciji s pretpostavkom zadatka. Isto vrijedi i za parove $299$ i $297$, $299$ i $296$, i tako sve do $299$ i $2$. Jasno je da je to neizvedivo jer osoba s $299$ poznanika tada ne bi znala nikoga osim osobe s jednim poznanikom. Probajmo ovo poopćiti i zapisati elegantnije kako bismo dobili gornju među za $n$ koju onda možemo potvrditi konstrukcijom grafa za taj konkretni slučaj. Osoba s $k$ poznanika ne poznaje barem osobe s $k-1, k-2, \ldots$ poznanika pa sve do $l$ dok zbroj njihovih poznanika ($k+l$) nije strogo veći od $300$ (za te slučajeve primjenjujemo Dirichletov princip i dobivamo kontradikciju s pretpostavkom zadatka — da nema trojice koji se međusobno poznaju). Dakle $k+1=301$, to jest, $l=301-k$, to jest osoba s $k$ osoba ne poznaje osobe s $k-1, k-2, \ldots, 301-k$ redom (barem). Njih ima $k-1-(301-k)+1=2k-301$, i dodatno, osoba ne poznaje samoga sebe, dakle ne poznaje još jednu osobu, pa ih sveukupno ne poznaje $2k-301+1=2k-300$, a možda i više. S druge strane, trivijalno, osoba u grupi od 300 osoba koja poznaje njih $k$ ne poznaje njih $300-k$, pa mora vrijediti $2k-300 \leq 300 -k$, što daje gornju granicu za $k$ od $200$ osoba.

Još je potrebno konstrukcijom grafa pokazati da je za $n=200$ to zaista moguće. Ostatak rješenja može se naći na ovoj poveznici.

Zadatak 6. (Državno natjecanje 2019, SŠ2A, 7. zadatak)
Između gradova prometuju jednosmjerne avionske linije. Za svaka dva grada $A$ i $B$ postoji točno jedna linija: ili iz $A$ prema $B$, ili iz $B$ prema $A$. Dokaži da postoji grad iz kojeg je moguće doći do bilo kojeg drugog grada s najviše jednim presjedanjem.

Uputa:
Dokažite da tvrdnja vrijedi za grad iz kojeg polazi najveći broj linija.

Rješenje: na poveznici.

Zadatak 7. (Državno natjecanje 2017, SŠ2A, 5.)
U jednom gradu je $M$ ulica i $N$ trgova, pri čemu su $M$ i $N$ prirodni brojevi takvi da je $M > N$. Svaka ulica povezuje dva trga i ne prolazi drugim trgovima. Građani žele promijeniti izgled grada. Ove godine svaka će ulica biti po prvi put obojena crveno ili plavo. Dogovoreno je da se svake godine odabere jedan trg, te svim ulicama koje vode do tog trga istovremeno promijeni boja iz plave u crvenu i obratno. Dokaži da građani mogu odabrati boje ulica tako da se nikad u budućnosti ne može dogoditi da sve ulice budu iste boje.

Uputa:
Promotrite parnost transformacija ili cikluse u grafu.

Rješenje: na poveznici.

Zadatk 8. (Državno natjecanje 2015, SŠ3A, 3.)
U nekoj državi između svaka dva grada postoji ili izravna autobusna ili izravna željeznička veza (sve veze su dvosmjerne i ne prolaze ni kroz jedan drugi grad). Dokaži da je gradove u toj državi moguće rasporediti u dva disjunktna skupa tako da je sve gradove u jednom skupu moguće obići putujući samo željeznicom tako da se nijedan grad ne posjeti dvaput, a sve gradove u drugom skupu putujući samo autobusom tako da se nijedan grad ne posjeti dvaput.

Uputa:
Odvojite gradove koje možete obići samo autobusom i one koje možete obići samo željeznicom i promatrajte par najvećih takvih skupova. Što ako oni ne obuhvaćaju sve gradove?

Rješenje: na poveznici.

Literatura

1. Dragana Biljuš – Teorija grafova i zadatci s natjecanja (diplomski rad)
2. Lucija Relić – Teorija grafova (MNM predavanje)
3. Vedran Krčadinac – skripta za kolegij Kombinatorika, PMF-MO
4. Kristina Škreb – Teorija grafova
5. Predavanja iz kolegija “Diskretna matematika” – PMF-MO
6. Proof by Contradiction Using Hall’s Marriage Theorem (Playing Cards) – Mathispowerful4u
7. Vježbe iz kolegija “Diskretna matematika” – PMF-MO
8. Zadatci s natjecanja

---