Teorija grafova ima dosta precizne povijesne odrednice. Prvi rad iz teorije grafova je Eulerovo1 rješenje pitanja šetnje koenigsberškim mostovima, objavljen 1736. godine, [5]. Prvu knjigu iz teorije grafova [8] napisao je 200 godina poslije D. Koenig2, što se smatra početkom razvoja teorije grafova kao zasebne matematičke discipline. Koenig je dotadašnje rezultate objedinio i sistematizirao, navodeći popis od svega 110 objavljenih radova u kojima se eksplicitno pojavljuje pojam grafa. Među njihovom autorima su slavna imena poput G. Kirhhoff, A. Cayley i C. Kuratowsky. Od tada graf postaje općenito prihvaćen pojam. Sljedećih tridesetak godina jezikom grafova su postavljani i rješavani brojni zanimljivi problemi o čemu primjerice svjedoči popis od 1617 referencija iz teorije grafova objavljen u [14] 1964. godine.

U 60-tim godinama dvadesetog stoljeća počinje snažan razvoj istraživanja u teoriji grafova i njenim primjenama koji traje do danas. U razdoblju od 1960. do 1970. broj godišnje objavljenih radova se više nego udeseterostručio. Danas imamo na desetke uglednih časopisa koji gotovo isključivo objavljuju članke iz teorije grafova i njenih primjena. Neobično intenzivan razvoj i veliku popularnost teorija grafova je doživjela zahvaljujući, izravno ili neizravno, naglom razvoju modernih informacijskih tehnologija. Jasna geometrijska predodžba koju graf sadržiava i koja je bliska intuitivnom poimanju osobina i veza objekata predstavljenih grafom pridonijela je širokom spektru primjene grafova. S druge strane, grafovi postaju univerzalni matematički jezik kojim je moguće opisati najrazličitije, i sasvim apstraktne matematičke strukture.

Ovdje ćemo usmjeriti pozornost na dvije slavne teme: šetnje koenigsberškim mostovima i problem kineskog poštara.

Građani Koenigsberga (tada glavni grad pruskog kraljevstva, a poslije Kalinjingrad u Rusiji) zabavljali su se starim pitanjem mogu li prošetati svojim gradom tako da svaki od 7 mostova na rijeci Pregel pređu točno jedanput i završe šetnju u polaznoj točki, Slika 1. Leonhard Euler riješio je taj problem kao usputni zadatak na početku karijere vodećeg matematičara Ruske carske akademije u Petrogradu, gdje je 1733. godine dobio posao. Odgovor je bio nedvosmislen: takva šetnja nije moguća ako svaki dio kopna nije s ostalima povezan parnim brojem mostova. Matematički oblik te tvrdnje iskazan je Teoremom 2. Shematski prikaz na Slici 2, na kojem su dijelovi kopna (obale B i C i otoci A i D) predstavljeni točkama a mostovi njihovim spojnicama, prototip je modela koji će odrediti definiciju pojma grafa. 

Početkom 60-tih godina dvadesetog stoljeća kineski matematičar M. Guan (Meigu Guan ili Mei-Ko Kwan) postavlja i proučava pitanje optimizacije poštarova puta pri dostavi pošiljki, [7]. Poštar kreće iz poštanskog ureda, dijeli poštu i vraća se u ured. Poštarov cilj je svakom ulicom proći barem jedanput i pri tome prijeći najkraći mogući put. U slučaju koenigsberških mostova analogan zadatak bi bio: prošetati gradom i vratiti se u polaznu točku prelazeći svaki most najmanje jedanput uz minimalan broj ponovljenih prelazaka. Guanovo pitanje doživjet će brojne modifikacije i imati raznovrsne primjene. Taj tip problema njemu u čast nazvan je Problem kineskog poštara, skraćeno CPP (engl. Chinese Postman Problem). Pod tim imenom je poznat kao jedan od najpopularnijih problema kombinatorne optimizacije. Optimizacijske probleme i kombinatorne probleme općenito relativno je lako formulirati, ali je njihovo rješavanje rijetko kada jednostavno. Za sustavno traženje rješenja potrebno je pronaći primjerene matematičke modele i metode. O matematičkim modelima motiviranima rješavanjem spomenutih problema govorimo u nastavku.




Vrhove u i v koji su pridruženi bridu e nazivamo krajevima brida e. Brid čiji se krajevi podudaraju nazivamo petljom. Višestruki bridovi su dva ili više njih s istim parom krajeva. Za par vrhova u i v kažemo da su susjedni ako postoji brid e kojemu su oni krajevi. Pri tome kažemo da je brid e incidentan s vrhovima u i v, za što ćemo upotrijebiti oznaku e=\left\lbrace u,v\right\rbrace ili e=uv. Stupanj vrha v  u grafu G je broj bridova grafa G incidentnih s v, pri čemu se svaka petlja računa kao dva brida. Izolirani vrh je vrh stupnja 0.

Šetnja u grafu G je niz W:=v_{0}e_{1}v_{1}e_{2}...e_{k}v_{k} čiji članovi su naizmjenično vrhovi v_{i} i bridovi e_{i}, tako da su krajevi od e_{i} vrhovi v_{i-1} i v_{i}, i=1,\ldots,k. Kažemo da je v_{0} početak a v_{k} kraj šetnje W, da je W šetnja od v_{0} do v_{k} ili \left( v_{0},v_{k}\right)-šetnja. Šetnja se, kada to ne umanjuje jasnoću, skraćeno zapisuje samo bridovima W=e_{1}e_{2}...e_{k}. Šetnja je zatvorena ako se početak i kraj podudaraju, tj. ako je v_{0}=v_{k}. Šetnju kojoj su svi bridovi međusobno različiti nazivamo stazom. Put je staza čiji su vrhovi međusobno različiti. Dva vrha u i v grafa G su povezana ako postoji \left( u,v\right)-put u G. Graf je povezan ako su svaka dva njegova vrha povezana.

Eulerova staza je staza koja sadržava svaki brid grafa (točno jedanput!). Eulerova tura u grafu je zatvorena Eulerova staza. Ako graf dopušta Eulerovu turu kažemo da je Eulerov graf.

Odgovor na pitanje koji graf ima Eulerovu turu ili Eulerovu stazu daje sljedeći karakterizacijski teorem.



Graf sa Slike 2, koji predstavlja koenigsberške mostove, ima sva četiri vrha neparnog stupjna. Na temelju Teorema 2 možemo ustvrditi da taj graf ne sadržava Eulerovu turu, ali ni Eulerovu stazu. Dakle, šetnja gradom koja prolazi svakim mostom točno jedanput nije moguća.

Rješavajući probleme "obilazaka gradskih ulica" nerijetko treba uzeti u obzir dodatni parametrar kao što je "dopušteni smjer". Traženje matematičkog modela za slične probleme prirodno vodi pojmu usmjerenog grafa.



Pojmove koje smo imali kod grafova analogno definiramo za digrafove. Dva ili više lukova s istim početkom i krajem su višestruki lukovi. Usmjerena šetnja u digrafu D je niz W:=v_{0} e_{1}v_{1}e_{2}...e_{k}v_{k} čiji članovi su naizmjenično vrhovi v_{i} i lukovi e_{i} tako da je početak od e_{i} vrh v_{i-1}, a kraj mu je v_{i}, i=1,\ldots,k. Kažemo da je v_{0} početak, a v_{k} kraj usmjerene šetnje W ili da je W\left( v_{0} ,v_{k}\right) usmjerena šetnja. Usmjerena šetnja je zatvorena ako je v_{0}=v_{k}. Usmjerenu šetnju kojoj su svi lukovi međusobno različiti nazivamo usmjerenom stazom. Usmjereni put je usmjerena staza čiji su vrhovi međusobno različiti. Usmjerena Eulerova tura je usmjerena zatvorena staza koja svaki luk digrafa sadržava točno jedanput. Eulerov digraf je onaj koji ima Eulerovu turu.

Pripadajući graf G\left( D\right) digrafa D je graf dobiven zamjenom svakog luka a=\left( u,v\right) bridom e=\left\lbrace u,v\right\rbrace. Digraf D je slabo povezan (kraće povezan) ako je pripadajući graf povezan, a jako povezan ako za svaka dva vrha u,v\in V\left( D\right) postoje \left( u,v\right) i \left( v,u\right) usmjereni putovi. Ulazni (izlazni) stupanj vrha v digrafa je broj lukova kojima je v kraj (početak).

Eulerov digraf ima karakterizaciju analognu onoj koju za Eulerov graf daje Teorem 2.



Smjer luka na skicama označavamo strelicom koja pokazuje od početka prema kraju luka. Jedan digraf prikazan je na Slici 4. Vidimo da taj digraf nije Eulerov jer ne zadovoljava uvjet o stupnjevima iz Teorema 4. Ako mu dodamo jedan luk \left( v,w\right) i jedan luk \left( z,y\right), novi digraf će biti Eulerov.

Opširnije o spomenutim pojmovima i tvrdnjama može se naći u brojnim knjigama iz teorije grafova kao što su [6] ili [16].



Vratimo se Problemu kineskog poštara na primjeru grafa za koenigsberške mostove, Slika 3. Pretpostavimo da je svaki brid u grafu ulica u kojoj treba isporučiti poštu, a vrh je mjesto gdje poštar može promijeniti smjer. Poštar mora proći svakom ulicom da bi isporučio poštu i želi minimizirati broj ponovnih prolazaka istom ulicom, koji se ne mogu izbjeći jer graf nije Eulerov. Ponovni prolazak istom ulicom prikazujemo na grafu kao dodani (ponovljeni) brid. Nastali višestruki bridovi omogućuju da svaki vrh novog grafa bude parnog stupnja, odnosno dodavanjem bridova je izvršena "eulerizacija" grafa. U modificiranom grafu može se odrediti Eulerova tura. Na primjer, traženi poštarov obilazak za Eulerov graf sa Slike 3 može biti a b c b e f g d d. U njemu se ponavljaju samo bridovi b i d.
Pri traženju najkraćeg poštarovog obilaska gradskih ulica treba uzeti u obzir parametre kao što su duljine ulica ili vrijeme potrebno za prolazak tim ulicama. Matematički model za ovaj i slične probleme je težinski graf.



Težine bridova težinskog grafa mogu predstavljati udaljenost, vrijeme, visinu nekih troškova i slično.



Dakle, osnovnmi oblik CPP-a svodi sena traženje optimalne poštarove ture u težinskom grafu. Ako je graf Eulerov, svaka Eulerova tura je optimalna poštarova tura pa je njenim pronalaskom problem riješen. Navest ćemo dva standardna algoritma za pronalaženje Eulerove ture, Fleuryjev i Hierholzerov. Pri tome ćemo se koristiti nekim pojmovima i oznakama iz teorije grafova koje do sada nismo spomenuli pa ih ovdje uvodimo.

Ako su G i H grafovi, V\left( H\right) \subseteq V\left( G\right), E\left( H\right) \subseteq E\left( G\right) i svaki brid iz H ima iste krajeve u H kao što ih ima u G, onda kažemo da je H podgraf od G. Neka je G=\left( V,E\right) i E^{\prime }\subseteq E. Podgraf od G čiji je skup vrhova V i skup bridova E\setminus E^{\prime} označavamo G-E. Ako je E^{\prime}=\left\lbrace e\right\rbrace, koristimo oznaku G-e. Komponenta povezanosti grafa G je maksimalni povezani podgraf od G, tj. povezani podgraf koji nije sadržan ni u jednom drugom povezanom podgrafu. Za broj komponenti povezanosti grafa G koristimo se oznakom c\left( G\right). Rezni brid u grafu G je brid e\in E\left( G\right) za koji je c\left( G-e\right) \gt c\left( G\right), tj. čijim se izostavljanjem povećava broj komponenti povezanosti.

 

Algoritam 1.

Fleuryjev algoritam

Ulaz: Eulerov graf G.

Izlaz: Eulerova tura C u grafu G.

Korak 1: Izabrati proizvoljni vrh v\in V(G). Postaviti v za tekući vrh i C:=v.

Korak 2: Označiti proizvoljni brid e koji je incidentan s tekućim vrhom i nije rezni brid te ga dodati stazi C. Samo ako nema drugih mogućnosti, za e uzeti rezni brid. Postaviti za tekući vrh drugi kraj brida e.

Korak 3: Izbrisati označeni brid iz G. Ako nema preostalih bridova: KRAJ; u suprotnom: povratak na Korak 2.
Hierholzerov algoritam traži Eulerovu turu u Eulerovom grafu bez provjere je li brid kojim prolazi rezni. Ovaj algoritam konstruira u grafu sukcesivno zatvorene staze čijim se spajanjem u konačnici dobije Eulerova tura.

 

Algoritam 2.

Hierholzerov algoritam 

Ulaz: Eulerov graf G.

Izlaz: Eulerova tura u grafu G.

Korak 1: Izabrati proizvoljni vrh v\in V(G).

Korak 2: Konstruirati zatvorenu stazu C_{0} u G s početkom u vrhu v. Postaviti\ i:=0.

Korak 3: Ako je E\left( C_{i}\right) =E\left( G\right) (C_{i} Eulerova tura u G): KRAJ.

Ako je E\left( C_{i}\right) \neq E\left( G\right) , odabrati vrh v_{i}\in C_{i} incidentan bridu e\notin C_{i} i konstruirati zatvorenu stazu C_{i}^{\ast} u grafu G-E\left( C_{i}\right) s početkom u vrhu v_{i}.

Korak 4: Spajanjem staza C_{i} i C_{i}^{\ast} konstruirati zatvorenu stazu C_{i+1} s početkom u vrhu v_{i-1}\in C_{i}; ići stazom C_{i} do v_{i}\in C_{i}, zatim preko svih bridova u C_{i}^{\ast} i potom svih preostalih bridova u C_{i}. Postaviti i:=i+1 i ići na Korak 3.  
Ako graf nije Eulerov, dodavanjem ponovljenih bridova može se prevesti u graf koji ima Eulerovu turu, što je bila Guanova polazna ideja, [7]. Ta procedura provodi se takozvanim CPP algoritmom. Sada, koristeći se Fleuryjevim algoritmom možemo naći Eulerovu turu u grafu. Polaskom iz vrha a imamo Eulerovu turu a-b-c-g-d-e-f-g-e-g-b-a-f-a. Budući da je to optimalna poštarova tura, dobili smo traženo rješenje.