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.   

Mnogi se životni problemi mogu modelirati uz pomoć grafova. Graf se sastoji od točaka i njihovih spojnica. Tako točke mogu biti ljudi u određenom društvu, a spojnice parovi prijatelja, ili točke mogu biti električne komponente, a spojnice električna mreža itd.

Grubo govoreći, graf je familija točaka, koje nazivamo vrhovima, zajedno sa spojnicama među njima, koje nazivamo bridovima. Precizna definicija glasi:



Ako su nekom bridu e\in E pridruženi vrhovi u,v\in V, kažemo da su u i v krajevi brida e. Kažemo još i da su vrhovi u i v incidentni s bridom e, da su u i v susjedni vrhovi te pišemo e=uv. Bridovi s barem jednim zajedničkim krajem zovu se susjedni bridovi. Brid čiji se krajevi podudaraju zove se petlja, a brid čiji su krajevi različiti pravi brid ili karika. Dva ili više bridova koji imaju isti par krajeva zovu se višestruki bridovi. Graf koji nema petlji i višestrukih bridova nazivamojednostavnim grafom. Mi ćemo se ovdje baviti samo jednostavnim grafovima i pod pojmom graf podrazumijevati samo takve grafove.




Primijetimo da je u jednostavnom grafu šetnja potpuno određena nizom svojih vrhova v_{0}v_{1}v_{2}...v_{m-1}v_{m}.



Da bismo dobili predodžbu o tome kakvim se problemima bavi teorija sparivanja, počnimo s dva jednostavna primjera koja dobro ilustriraju taj problem.




Ako izvršitelje i poslove, odnosno djevojke i momke, uzmemo za vrhove grafa, a bridovima spojimo svakog izvršitelja s poslovima koje zna obavljati, odnosno sve djevojke i momke koji se međusobno simpatiziraju, onda naš problem glasi: odredite maksimalan broj bridova od kojih nikoja dva nisu susjedna.





Ako je E\neq\emptyset, onda je svaki jednočlani podskup od E jedan primjer sparivanja u G. No, zanimljivo je naći sparivanje sa što većim brojem bridova. Stoga definiramo:




U literaturi se savršeno sparivanje često zove Kekuléova struktura, prema njemačkom kemičaru Augustu Kekuléu (1829. – 1896.).

Očito je svako savršeno sparivanje ujedno i maksimalno, dok obrat općenito ne vrijedi. Nadalje, broj bridova u savršenom sparivanju je konstantan i iznosi \frac{\left\vert V\right\vert }{2}. Za postojanje savršenog sparivanja nužno je da graf ima paran broj vrhova. No, to je samo nuždan, a ne i dovoljan uvjet za postojanje savršenog sparivanja. Osnovni problem teorije sparivanja jest ispitati postoji li savršeno sparivanje i ako postoji, konstruirati ga. U slučaju da se ne može konstruirati savršeno sparivanje, cilj je konstruirati sva ili bar neka maksimalna sparivanja.



Označimo s

\bullet	v(G)= kardinalnost maksimalnog sparivanja u G,
\bullet	\alpha(G)= kardinalnost maksimalnog stabilnog skupa u G,
\bullet	\tau(G)= kardinalnost minimalnog vršnog pokrivača od G,
\bullet	\rho(G)= kardinalnost minimalnog bridnog pokrivača od G.

Primijetimo da je \rho(G) dobro definiran samo za grafove bez izoliranih vrhova.

Neka je K neki vršni pokrivač grafa G, a M neko sparivanje u G. Tada svaki brid iz M ima barem jedan kraj u K, a budući da bridovi iz M nemaju zajedničkih vrhova, to je \left\vert M\right\vert \leq\left\vert K\right\vert. Stoga i za maksimalno sparivanje M^{\ast} i minimalni vršni pokrivač \bar{K} također vrijedi \left\vert M^{\ast}\right\vert \leq\left\vert \bar{K}\right\vert, tj. \upsilon (G)\leq\tau(G).

Slično, ako je L bridni pokrivač grafa G, a S stabilan skup, onda je \left\vert S\right\vert \leq\left\vert L\right\vert jer je svaki vrh iz S kraj barem jednom bridu iz L, a nikoja dva vrha iz S nisu susjedna. Stoga je \alpha(G)\leq\rho(G). Nadalje, vrijedi teorem



Iz ovog odmah slijedi da je \alpha(G)+\tau\left( G\right) =\left\vert V\right\vert . Slično, v(G)+\rho\left( G\right) =\left\vert V\right\vert, tj. kardinalnost maksimalnog sparivanja i minimalnog bridnog pokrivača u sumi daju ukupan broj bridova grafa G, iako komplement sparivanja ne mora biti bridni pokrivač, kao što je slučaj sa stabilnim skupom i vršim pokrivačem.

Jedan od osnovnih pojmova teorije sparivanja je pojam uvećavajućeg puta.




Ovaj teorem omogućuje nam da provjerimo je li neko sparivanje M u grafu G maksimalno, kako bismo ispitali postoji li ili ne M-uvećavajući put.




Vidjeli smo da u svakom grafu vrijedi nejednakost \upsilon(G)\leq\tau(G). No, sljedeći teorem kaže da u bipartitnom grafu vrijedi \upsilon (G)=\tau(G).




Potpuno sparivanje, dakle, definira jedno 1-1 preslikavanje između vrhova iz X i jednog dijela vrhova iz Y koje odgovarajuće vrhove iz X i Y spaja bridom. Stoga za svakih k vrhova iz X mora postojati barem k njima susjednih vrhova u Y. To je, dakle, nuždan uvjet za postojanje potpunog sparivanja. Sljedeći teorem kazuje da je to i dovoljan uvjet.



Ako particije X i Y imaju jednak broj elemenata, onda su potpunim sparivanjem u X zasićeni i svi vrhovi iz Y, pa je riječ o savršenom sparivanju u bipartitnom grafu. O tome govori sljedeći teorem popularno nazvan Teorem o braku.



Primjenjujući ovaj teorem na uvodne primjere 4 i 5, lako ćemo odgovoriti na pitanja koja se u njima postavljaju. Označimo li sa K=\left\lbrace K_{1},K_{2},K_{3},K_{4},K_{5}\right\rbrace skup svih kandidata, a sa P=\left\lbrace P_{1},P_{2},P_{3},P_{4},P_{5}\right\rbrace skup svih poslova, tada problem možemo predstaviti bipartitnim grafom G=\left( K,P\right), a pitanje je li moguće rasporediti kandidate na poslove tako da svi kandidati obavljaju posao za koji su kvalificirani i da se svi poslovi obavljaju, ekvivalentno je pitanju postoji li u tom grafu savršeno sparivanje. Pogledajmo skup S=\left\lbrace K_{1},K_{2},K_{4}\right\rbrace \subset K. Kako je kandidat K_{1} kvalificiran za poslove P_{3},P_{4}, kandidat K_{2} za posao P_{3}, a kandidat K_{4} za poslove P_{3},P_{4}, tako je skup svih vrhova koji su susjedni skupu S jednak N\left( S\right) =\left\lbrace P_{3},P_{4}\right\rbrace. Stoga je \left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert, pa nije zadovoljen Hallov uvjet, što znači da ne postoji savršeno sparivanje u ovom grafu. Dakle, nije moguće rasporediti kandidate na poslove tako da svi kandidati obavljaju posao za koji su kvalificirani, a da se svi poslovi obavljaju.

No, u bipartitnom grafu koji odgovara problemu iz Primjera 4 vrijedi Hallov uvjet za svaki podskup skupa djevojaka, pa stoga postoji savršeno sparivanje u tom grafu, tj. možemo povezati sve parove poštujući navedene simpatije. Naravno, sada se postavlja pitanje kako konstruirati to sparivanje. Sam Hallov uvjet bez dodatnih razmatranja ne bi bio koristan u praksi jer za bipartitni graf G\left( X,Y\right) treba ispitati sve podskupove skupa X, a broj podskupova naglo raste kako raste broj vrhova. Tako bi, naprimjer, za graf kojemu je \left\vert X\right\vert =50 trebalo ispitati 1125899906842623 različitih podskupova od X.


Pored samog pitanja egzistencije savršenog sparivanja u bipartitnom grafu, jednako je važno i pitanje njegove konstrukcije u slučaju da takvo sparivanje postoji. Jedna od poznatih metoda koja se bavi pitanjima egzistencije i konstrukcije savršenog sparivanja u bipartitnom grafu je tzv. mađarska metoda. S pomoću nje se ili konstruira savršeno sparivanje u bipartitnom grafu G\left( X,Y\right), ili se pronađe podskup S\subseteq X za koji je \left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert, pa po Hallovu teoremu slijedi da savršeno sparivanje u G\left( X,Y\right) ne postoji.

Ideja je sljedeća:

Započnemo s nekim sparivanjem M u bipartitnom grafu G\left( X,Y\right), pri čemu za M možemo uzeti i prazan skup ako ne znamo ništa bolje. Ako M zasićuje X, onda je ono i savršeno sparivanje, pa smo gotovi. Ako, pak, postoji M-nezasićen vrh u\in X, onda algoritam sustavno traži M-uvećavajući put P s početkom u vrhu u. Ako takav put postoji, onda za sparivanje M^{\prime}=M\bigtriangleup E\left( P\right), gdje je E\left( P\right) skup bridova puta P, sadržava više bridova i zasićuje više vrhova u X nego sparivanje M. Tako dobivamo veće sparivanje M^{\prime}, a potom cijeli postupak ponovimo tako da umjesto polaznog sparivanja M uzmemo sparivanje M^{\prime }. U slučaju da takav put ne postoji, pronađemo skup R svih vrhova koji su s vrhom u povezani M-alternirajućim putom. Može se pokazati da za skup S=R\cap X vrijedi \left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert, pa po Hallovu teoremu zaključujemo da ne postoji savršeno sparivanje u bipartitnom grafu G\left( X,Y\right), a po Teoremu 12 da je sparivanje M maksimalno sparivanje u G.

Ovaj algoritam dao je J. Edmonds 1965. godine, a zove se mađarska metoda jer se zasniva na idejama dvojice Mađara: Kőniga i Egerváryja.

Algoritam:

Ulaz. Bipartitni graf G s biparticijom (X,Y), \left\vert X\right\vert =\left\vert Y\right\vert.

Izlaz. Savršeno sparivanje M u G ili skup S\subseteq X za koji je \left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert.


Korak 1. Neka je M bilo koje sparivanje od G, npr. M=\emptyset.

Korak 2. Ako je XM-zasićen, stop (M je tada savršeno sparivanje od G).

U protivnom, neka je vrh x\in XM-nezasićen.

Stavimo S=\left\lbrace x\right\rbrace ,T=\emptyset.

Korak 3. Ako je N\left( S\right) =T, stop (\left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert).

U protivnom, neka je y\in N\left( S\right) \setminus T.

Korak 4. Ako je y\in YM-zasićen vrh, neka je zy\in M.

Zamijenimo S sa S\cup\left\lbrace z\right\rbrace, a T sa T\cup\left\lbrace y\right\rbrace i vratimo se na korak 3.

Ako je yM-nezasićen vrh, neka je PM-uvećavajući (x,y)-put.

Zamijenimo M s M\bigtriangleup E\left( P\right) i vratimo se na korak 2.


Pogledajmo kako ovaj algoritam radi na primjeru naših djevojaka i momaka.


Ulaz. Bipartitni graf G(X,Y), X=\left\lbrace D_{1},D_{2},D_{3} ,D_{4}\right\rbrace ,Y=\left\lbrace M_{1},M_{2},M_{3},M_{4}\right\rbrace.


Korak 1. Neka je M=\emptyset.

Korak 2. X nije M-zasićen. Vrh x=D_{1}\in X je M-nezasićen.

Stavimo S=\left\lbrace D_{1}\right\rbrace ,T=\emptyset.

Korak 3. N\left( S\right) =\left\lbrace M_{2},M_{3}\right\rbrace \neq T=\emptyset.

Neka je y=M_{2}\in N\left( S\right) \setminus T=\left\lbrace M_{2},M_{3}\right\rbrace.

Korak 4. y je M-nezasićen vrh. Neka je P=D_{1}M_{2}M-uvećavajući put.

\qquad\qquad M=\left\lbrace D_{1}M_{2}\right\rbrace i vratimo se na korak 2.

Korak 2. X je M=\left\lbrace D_{1}M_{2}\right\rbrace-nezasićen. Vrh x=D_{2}\in X je M-nezasićen.

Stavimo S=\left\lbrace D_{2}\right\rbrace ,T=\emptyset.

Korak 3. N\left( S\right) =\left\lbrace M_{2},M_{4}\right\rbrace \neq T=\emptyset.

Neka je y=M_{2}\in N\left( S\right) \setminus T=\left\lbrace M_{2},M_{4}\right\rbrace.

Korak 4. y=M_{2} je M-zasićen vrh jer je D_{1}M_{2}\in M.

S=S\cup\left\lbrace D_{1}\right\rbrace =\left\lbrace D_{1} ,D_{2}\right\rbrace ,T=T\cup\left\lbrace M_{2}\right\rbrace =\left\lbrace M_{2}\right\rbrace

Vratimo se na korak 3.

Korak 3. N\left( S\right) =N\left( \left\lbrace D_{1},D_{2}\right\rbrace \right) =\left\lbrace M_{2},M_{3},M_{4}\right\rbrace \neq T=\left\lbrace M_{2}\right\rbrace

Neka je y=M_{3}\in N\left( S\right) \setminus T=\left\lbrace M_{3},M_{4}\right\rbrace

Korak 4. y=M_{3} je M-nezasićen.

Neka je P=D_{2}M_{2}D_{1}M_{3}M-uvećavajući (D_{2},M_{3})-put.

M=M\vartriangle E\left( P\right) =\left\lbrace D_{1} M_{3},D_{2}M_{2}\right\rbrace i vratimo se na korak 2.

Korak 2. X jeM=\left\lbrace D_{1}M_{3},D_{2}M_{2}\right\rbrace-nezasićen.

Vrh x=D_{3}\in X je M-nezasićen.

Stavimo S=\left\lbrace D_{3}\right\rbrace ,T=\emptyset.

Korak 3. N\left( S\right) =\left\lbrace M_{1},M_{4}\right\rbrace \neq T=\emptyset.

Neka je y=M_{1}\in N\left( S\right) \setminus T=\left\lbrace M_{1},M_{4}\right\rbrace.

Korak 4. y=M_{1} je M-nezasićen vrh.

P=D_{3}M_{1} je M-uvećavajući (D_{3},M_{1} )-put, E\left( P\right) =\left\lbrace D_{3}M_{1}\right\rbrace

M=M\vartriangle E\left( P\right) =\left\lbrace D_{1} M_{3},D_{2}M_{2},D_{3}M_{1}\right\rbrace i vratimo se na korak 2.

Korak 2. X je M=\left\lbrace D_{1}M_{3},D_{2}M_{2},D_{3}M_{1}\right\rbrace-nezasićen.

Vrh x=D_{4}\in X je M-nezasićen.

Stavimo S=\left\lbrace D_{4}\right\rbrace ,T=\emptyset.

Korak 3. N\left( S\right) =\left\lbrace M_{1}\right\rbrace \neq T=\emptyset.

Neka je M_{1}\in N\left( S\right) \setminus T=\left\lbrace M_{1}\right\rbrace.

Korak 4. y=M_{1} je M-zasićen vrh jer je D_{3}M_{1}\in M.

S=S\cup\left\lbrace D_{3}\right\rbrace =\left\lbrace D_{3} ,D_{4}\right\rbrace ,T=T\cup\left\lbrace M_{1}\right\rbrace =\left\lbrace M_{1}\right\rbrace

Vratimo se na korak 3.

Korak 3. N\left( S\right) =N\left( \left\lbrace D_{3},D_{4}\right\rbrace \right) =\left\lbrace M_{1},M_{4}\right\rbrace \neq T=\left\lbrace M_{1}\right\rbrace

Neka je y=M_{4}\in N\left( S\right) \setminus T=\left\lbrace M_{4}\right\rbrace

Korak 4. y=M_{4} je M-nezasićen.

P=D_{4}M_{1}D_{3}M_{4} je M-uvećavajući (D_{4},M_{4})-put, E\left( P\right) =\left\lbrace D_{4}M_{1},D_{3}M_{1} ,D_{3}M_{4}\right\rbrace,

M=M\vartriangle E\left( P\right) =\left\lbrace D_{1} M_{3},D_{2}M_{2},D_{3}M_{4},D_{4}M_{1}\right\rbrace,

vratimo se na korak 2.

Korak 2. X je M=\left\lbrace D_{1}M_{3},D_{2}M_{2},D_{3}M_{4},D_{4} M_{1}\right\rbrace-zasićen, pa smo gotovi.

M je savršeno sparivanje.


Primijetimo da nam Mađarska metoda daje samo egzistenciju jednog savršenog sparivanja, no ne kaže nam ništa o broju svih mogućih savršenih sparivanja. U praksi nam može biti od važnosti poznavati njihov broj. O tome više u sljedećem poglavlju.


U daljnjem ćemo tekstu najviše pozornosti posvetiti molekularnim grafovima, pa ćemo se za savršena sparivanja koristiti izraz Kekuléove strukture. Kekuléove strukture igraju posebno važnu ulogu u proučavanju benzenoida. Benzenoidni graf je povezani graf čije se ravninsko smještanje sastoji od kongruentnih pravilnih šesterokuta, tako da svaka dva šesterokuta ili imaju zajednički vrh, ili su disjunktni. U literaturi ih ponekad nazivaju i poliheksi, heksagonalne životinje, heksagonalna poliomina, heksagonalni sustavi i sl. Za benzenoid kažemo da je katakondenziran ako nijedan vrh nije incidentan s tri šesterokuta. Za benzenoid kažemo da je benzenoidni lanac ako je katakondenziran i nijedan šeterokut nema tri susjedna šesterokuta. Prebrojavanje savršenih sparivanja ima važne kemijske primjene. Naime, Linus Pauling (dobitnik dviju Nobelovih nagrada) uočio je da se s pomoću Paulingova reda veze (omjer broja Kekuléovih struktura koje udvostručavaju neku vezu i svih Kekuléovih struktura) može izračunati aproksimacija duljine veze među atomima ugljika u benzenoidnim molekulama.


Označimo s G neki molekularni graf, a sa k podgraf koji čini Kekuléovu strukturu, tj. koji se sastoji od nesusjednih bridova grafa G, a svaki vrh grafa G je incidentan s točno jednim bridom u k. Naprimjer, za naftalen se mogu pronaći tri Kekuléove strukture.

S K\left( G\right) označimo broj svih različitih Kekuléovih struktura u grafu G. Da bismo odredili taj broj poslužit ćemo se linearnim rekurzijama na grafu i njegovim podgrafovima. Od samih početaka pa sve do danas, metode za prebrojavanje Kekuléovih struktura temelje se upravo na takvim rekurzijama.

Neka je e proizvoljan brid grafa G. S G-e označimo graf koji se dobije iz grafa G kada mu uklonimo brid e, a s G\circleddash e graf koji se dobije iz grafa G uklanjanjem brida e i svih njemu susjednih bridova. Tada vrijedi jednostavna rekurzija koju je i vrlo lako programirati. Važno je napomenuti da ako se primjenom ove rekurzije na neki izabrani niz bridova grafa G taj graf razbije u nepovezane dijelove, rekurziju tada možemo primijeniti zasebno na svaki njegov pojedini dio. Kod molekularnih grafova pozornost se posvećuje i dobivanju rekurzivne formule za prebrojavanje Kekuléovih struktura u ovisnosti o duljini lanca. Tako Gordonova i Davisonova shema za određivanje broja Kekuléovih struktura u katakondenziranom benzenoidnom lancu ima lagan i praktičan grafički prikaz. Pogledajmo to na sljedećem primjeru. Postupak izgleda ovako:

(1)	U šesterokute grafa koji prikazuje katakondenzirani benzenoidni lanac upisuju se brojevi počevši od jednog kraja i to na način: izvan početnog šesterokuta upiše se broj 1, a u prvi šesterokut upiše se broj 2.
(2)	Svaki broj u ostalim šesterokutima dobije se kao suma onog broja koji je upisan u šesterokut koji je njegov direktni prethodnik (njih dva određuju smjer) i onog koji je upisan u šesterokut neposredno prije skretanja lanca u tom smjeru.
(3)	Broj koji je upisan u zadnji šesterokut lanca upravo je broj Kekuléovih struktura K(G).

U našem primjeru je K(G)=25.



Linearna rekurzija K(G)=K(G-e)+K(G\circleddash e) u slučaju grafova polimera (lanac s mnogo ponavljajućih elemenata — ponavljajuće elemente nazivamo monomerima) ima vrlo elegantan oblik bez obzira na to kakvi su polimeri u pitanju. Mi ćemo se ovdje fokusirati na regularne polimere u kojima se ponavlja ista jedinica monomera. Broj Kekuléovih struktura K_{L} za ciklički lanac polimera duljine L se može izraziti u obliku gdje je T transfer matrica karakteristična za jedinicu određenog monomera, a \rho matrica koja opisuje karakter rubnih uvjeta, npr. krajeva lanca polimera.

Iz matrice T vidljivi su svi različiti načini na koje se Kekuléove strukture mogu načiniti iz jednog uzorka na granici jedne jedinice monomera do drugog uzorka na granici sljedeće jedinice monomera.


Taj lanac može se podijeliti na ćelije monomera kao na slici.


S obzirom na vertikalnu os simetrije ovih šesterokuta razlikujemo lijevi i desni monomer. S lijeve i desne strane osi simetrije je neparan broj vrhova šesterokuta (3), pa moramo imati i neparan broj dvostrukih bridova (bridova u sparivanju) koji sijeku os simetrije. Budući da samo dva lijeva brida sijeku os simetrije, točno je jedan od njih dvostruki brid. Sve mogućnosti za postavljanje dvostrukih veza na granici monomera prikazane su na sljedećoj slici.


U slučaju da je gornji lijevi brid koji siječe os simetrije dvostruki brid, postoje dva načina za nastavak na sljedećoj granici, dok se u slučaju donjeg lijevog dvostrukog brida može nastaviti samo na jedan način jer propada mogućnost donja lijeva dvostruka veza\rightarrow gornja desna dvostruka veza. Naime, ta nas mogućnost dovodi do nezasićenog vrha (vidite donju sliku). Vrhove A i B ne smijemo spojiti dvostrukim bridom jer već imamo jednu dvostruku vezu koja siječe os simetrije, a znamo da može biti samo jedna takva. To znači da vrh B ostaje nezasićen, pa ta mogućnost ne daje savršeno sparivanje.


Dakle, transfer matrica je oblika
Za uske lance (široke par šesterokuta) postoji tek nekoliko mogućih uzoraka, tako da je matrica T malog reda, a nakon njene dijagonalizacije lako se izračuna i tražena potencija matrice T za proizvoljnu duljinu lanca L. No, s povećanjem širine trake w, tj. broja veza koje presijecaju os simetrije, eksponencijalno se povećava i red matrice T, ali ova tehnika sigurno je primjenjiva za širine w\leq 12.



Lijevo od osi simetrije imamo neparan broj vrhova šesterokuta (ima ih 5), pa moramo imati i neparan broj dvostrukih bridova (bridova u sparivanju) koji sijeku os simetrije. Dakle, imamo jedan ili tri dvostruka brida koja sijeku os simetrije. Ispitajmo svaku mogućnost zasebno. Najprije pogledajmo sve mogućnosti u kojima je samo gornji lijevi brid dvostruki:


Očito, sve tri mogućnosti zasićuju sve vrhove, tj. vode do savršenog sparivanja.

Mogućnost srednja lijeva dvostruka veza\rightarrow gornja desna dvostruka veza nije dobra (slika 3). Naime, ta mogućnost dovodi nas do nezasićenog vrha. Vrh A ne možemo zasititi jer već imamo jednu dvostruku vezu koja siječe simetralu, a znamo da u ovom slučaju može biti samo jedna (situaciju s tri dvostruka brida zasebno ćemo ispitati). To znači da vrh A ostaje nezasićen, pa ta mogućnost ne daje savršeno sparivanje.

Ostale dvije mogućnosti (slika 4) srednja lijeva dvostruka veza\rightarrow srednja desna dvostruka veza i srednja lijeva dvostruka veza\rightarrow donja desna dvostruka veza su u redu i dovode nas do savršenog sparivanja.

Sljedeće mogućnosti počinju s donjim lijevim dvostrukim bridom. U prva dva slučaja (slika 5):
donja lijeva dvostruka veza\rightarrow gornja desna dvostruka veza i donja lijeva dvostruka veza\rightarrow srednja desna dvostruka veza nije moguće savršeno sparivanje jer dobivamo nezasićene vrhove (vrh A), dok je situacija donja lijeva dvostruka veza\rightarrow donja desna dvostruka veza u redu.

I napokon, ako su sva tri lijeva brida koja sijeku os simetrije dvostruki bridovi (slika 6), onda sve mogućnosti kad je na desnoj strani samo jedan dvostruki brid ili sva tri, dovode do nezasićenih vrhova početnih i krajnjih šesterokuta.

Dakle, transfer matrica je oblika što možemo poistovjetiti s matricom reda 3 oblika Lako se provjeri da je pa dobivamo broj Kekuléovih struktura u lancu duljine L u eksplicitnom obliku
Uočimo da je ova eksplicitna jednadžba analogna linearnoj rekurziji 1. Ako označimo karakteristični polinom transfer matrice reda n s onda je, po Hamilton-Cayleyevu teoremu, T^{n}=\sum\limits_{i=1}^{n} a_{i}T^{n-i}, pa je
što je prvobitna linearna rekurzija 1.

Za naš primjer strukture polifena je K_{L+1}=K_{L}+K_{L-1}. Primijetimo da je rekurzija uvelike neovisna o krajevima lanca, ali oni utječu na početne vrijednosti na kojima se rekurzija temelji.

Problem optimalne zamjene opreme jedan je od osnovnih problema u cjelokupnoj industriji. Sastoji se u određivanju optimalnoga trenutka zamjene stare opreme novom pod uvjetima da se opseg proizvodnje poveća, a troškovi proizvodnje umanje, tako da se time potpuno nadoknade troškovi kupnje nove opreme, gubici uzrokovani zastojem u proizvodnji zbog uvođenja nove opreme i troškovi obuke djelatnika za rad na novoj opremi.

Temeljni zadatak je odrediti optimalnu politiku modernizacije i zamjene opreme prihvaćajući pritom različite uvjete vezane za tekuće održavanje, karakteristike proizvodnje i predviđeni tehnološki razvoj. Ovakav proces očito zahtijeva analizu u više faza, pa se time dinamičko programiranje nameće kao prikladan način rješavanja ovakvih problema.

Neki tipovi problema zamjene opreme i načini njihova rješavanja ilustriraju se na sljedećim primjerima. U rješenjima pojedinih primjera koriste se računalni programi Graph Magics i Grin čije su besplatne probne (trial) verzije dostupne za preuzimanje putem Interneta.



Utvrđena poslovna politika neke tvrtke predviđa korištenje automobila u sljedećih n = 5 godina, pa je na početku prve godine razdoblja planiranja kupljen novi automobil po nabavnoj cijeni od p = 12 n.j.1 Radi jednostavnosti, pretpostavlja se da je nabavna cijena automobila stalna tijekom cijeloga razdoblja planiranja te da će po isteku razdoblja planiranja automobil obavezno biti rashodovan. Godišnji neto troškovi održavanja automobila (c_{i}) i likvidacijska vrijednost2 automobila (s_{i}) iskazani su kao funkcija starosti automobila:


Niz (c_{i})_{i \in \mathbb{N}} nužno je rastući, tj. povećanjem starosti automobila povećavaju se i godišnji troškovi njegova održavanja. Zbog tog razloga nakon određenog vremena može biti ekonomski isplativije rashodovati do tada korišteni automobil i kupiti novi. S druge je strane niz (s_{i})_{i \in \mathbb{N}} nužno padajući, tj. povećanjem starosti automobila smanjuje se njegova likvidacijska vrijednost.

Politika zamjene u ovome je slučaju donošenje odluke treba li zadržati postojeći automobil ili ga rashodovati i kupiti novi automobil. Navedeno odlučivanje na dnevni red dolazi početkom svake pojedine godine. Najjednostavniji primjeri politika zamjene su:

P_{1}) zamjena automobila, tj. rashodovanje do tada korištenoga automobila i kupnja novoga početkom svake pojedine godine (tj. početkom druge, treće, četvrte i pete godine);

P_{2}) zadržavanje postojećeg automobila sve do kraja pete godine.

U razmatranom je primjeru početkom prve godine već donesena odluka o kupnji novog automobila. Stoga se odluke donose početkom svake od sljedeće četiri godine. Budući da je početkom svake od tih godina moguće donijeti točno dvije različite odluke, postoji ukupno 16 međusobno različitih politika zamjene. Stoga je od interesa odrediti najbolju među njima, tj. odrediti optimalnu politiku zamjene.

Optimalna politika zamjene je politika zamjene koja osigurava najmanje ukupne neto troškove uporabe automobila tijekom svih pet godina. U promatranom primjeru to znači ispitati svih 16 međusobno različitih politika zamjene i među njima odrediti najbolju. No, takva je metoda za iole veće vrijednosti n općenito vrlo spora i neučinkovita, pa se stoga nameće problem iznalaženja dovoljno učinkovitih metoda i algoritama za određivanje optimalne politike. U tu se svrhu primjenjuju metode i tehnike dinamičkoga programiranja.

Primjer 1 može se riješiti «klasično», tj. definiranjem odgovarajućih rekurzivnih relacija, ali ovdje će biti riješen svođenjem na problem najkraćega puta u grafu. Matematički model koji će se koristiti je potpuni težinski digraf. Vrhovi toga digrafa predstavljat će početke godina, tj. vrh i označavat će početak godine i. Budući da se korištenje automobila planira u sljedećih n = 5 godina, graf će imati ukupno n + 1 = 6 vrhova: 1, 2, 3, 4, 5 i 6. Nadalje, za svaki uređeni par (i, j) takav da je i \lt j vrhovi i i j bit će spojeni usmjerenim bridom (lukom) čiji je početak u vrhu i, a kraj u vrhu j. Ukupan broj međusobno različitih lukova u tako dobivenom modelu jednak je Preostaje definirati težinu svakog od dobivenih lukova. Budući da treba minimizirati ukupne neto troškove, težina w_{ij} luka (i, j) definira se kao: Odatle slijedi da je analitički izraz za izračunavanje težina w_{ij}: Ovdje prešutno pretpostavljamo da se kraj godine k podudara s početkom godine (k + 1).

U razmatranom se primjeru pretpostavlja da je nabavna cijena automobila na početku svake godine ista i jednaka 12 n.j., tj. vrijedi jednakost p_{1} = p_{2} = p_{3} = p_{4} = p_{5} = p = 12. Zbog toga vrijedi i jednakost: za sve i,j,k za koje su definirane obje strane jednakosti. Tako se dobiva:
Za rješavanje primjera u nastavku koristimo se računalnim programom Graph Magics. Koristeći se njime, modeliramo navedeni problem potpunim težinskim digrafom, koji je prikazan na slici 1.

Radi određivanja najkraćega puta, vrh 1 označi se kao početni vrh, a vrh 6 kao završni vrh. Koristeći se procedurom Find Shortest Path (from Start Vertex to End) određuje se najkraći put između vrhova 1 i 6:


Njegova je težina jednaka 31. Unutrašnji vrhovi dobivenoga najkraćeg puta su 2 i 4, što znači da početkom tih godina treba rashodovati dotad korišteni automobil i zamijeniti ga novim. Prema tome, optimalna politika zamjene glasi:

\bullet	početak 2. godine: rashodovanje dotad korištenog automobila i kupnja novoga;
\bullet	početak 3. godine: zadržavanje dotad korištenog automobila;
\bullet	početak 4. godine: rashodovanje dotad korištenog automobila i kupnja novoga;
\bullet	početak 5. godine: zadržavanje dotad korištenog automobila;
\bullet	kraj 5. godine/početak 6. godine: rashodovanje dotad korištenog automobila.

Rješavanje «klasičnim» putem daje još jedan najkraći put:


U ovom slučaju na početku treće i na početku pete godine razdoblja planiranja treba rashodovati dotad korišteni automobil i zamijeniti ga novim, tj. optimalna politika zamjene glasi:

\bullet	početak 2. godine: zadržavanje dotad korištenog automobila;
\bullet	početak 3. godine: rashodovanje dotad korištenog automobila i kupnja novoga;
\bullet	početak 4. godine: zadržavanje dotad korištenog automobila;
\bullet	početak 5. godine: rashodovanje dotad korištenog automobila i kupnja novoga;
\bullet	kraj 5. godine/početak 6. godine: rashodovanje dotad korištenog automobila.

Obje navedene optimalne politike postižu najmanji iznos ukupnih neto troškova 31 n.j.



Usporedno s redovnim studiranjem Ivan je putem Student–servisa dobio honorarni posao dostavljača lokalnih besplatnih novina, oglasnoga materijala itd. Za taj mu je posao potreban bicikl koji trenutačno ne posjeduje. Trenutačna cijena novoga bicikla je p = 500 n.j. Novi bicikl može se koristiti najviše 3 godine, a potom ga treba prodati. Godišnji neto trošak održavanja bicikla i likvidacijska vrijednost bicikla, iskazani kao funkcije starosti bicikla, navedeni su u sljedećoj tablici:


Ako Ivan namjerava završiti svoj studij za točno 5 godina i dotad honorarno raditi kao dostavljač, treba odrediti optimalnu politiku zamjene bicikla tijekom razdoblja od 5 godina (pretpostavlja se da je cijena novoga bicikla stalna u cjelokupnom razdoblju planiranja te da će Ivan na kraju razdoblja planiranja obavezno prodati bicikl).

Prije rješavanja zadatka korisno je napraviti jednostavnu analizu kojom se pokušava utvrditi koje je «trajanje vlasništva» najekonomičnije, tj. je li općenito bolje zadržati bicikl 1, 2 ili 3 godine?

Kupi li Ivan bicikl, bude li ga koristio jednu godinu i potom ga prodao, prosječan (zapravo ukupan) godišnji neto trošak iznosit će p + c_{0} - s_{1} = 500 + 30 - 400 = 130 n.j.

Kupi li Ivan bicikl, bude li ga koristio ukupno dvije godine i potom ga prodao, prosječan godišnji neto trošak iznosit će
Ako Ivan kupi bicikl, bude li ga koristio sve tri godine i potom ga prodao, prosječan godišnji neto trošak iznosit će
Ova analiza pokazuje da je najisplativije zadržati bicikl sve tri godine i potom ga prodati, a ako to nije moguće, onda je najisplativije zadržati bicikl točno jednu godinu. Budući da je razdoblje planiranja n = 5 godina, može se procijeniti da će optimalna politika zamjene biti «kombinacija» jednogodišnjeg i trogodišnjeg trajanja vlasništva.

I u ovom se slučaju problem modelira težinskim digrafom, ali taj digraf neće biti potpun. Naime, bicikl se može koristiti najviše tri godine, a to je razdoblje strogo manje od razdoblja planiranja. Stoga neki vrhovi digrafa neće biti spojeni niti jednom spojnicom. Vrhovi digrafa ponovo će označavati početke godina, pa će graf imati ukupno n + 1 = 6 vrhova. Vrh i označavat će početak godine i (pritom se pretpostavlja da se kraj pete godine podudara s početkom šeste godine). Budući da se bicikl može koristiti najviše 3 godine, luk (i, j) postoji ako i samo ako vrijedi nejednakost 0 \lt j - i \leq 3. Stoga je skup svih lukova grafa jednak E = \lbrace (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)\rbrace. Težine pojedinih lukova izračunavaju se kao u primjeru 1:
Težinski digraf dobiven uz pomoć programa Graph Magics prikazan je na slici 2.
Najkraći put između vrhova 1 i 6 je


čija je težina 640. Prema tome, optimalna politika zamjene bicikla je sljedeća:

\bullet	početak 2. godine: prodaja dotad korištenoga bicikla i kupnja novoga bicikla;
\bullet	početak 3. godine: prodaja dotad korištenoga bicikla i kupnja novoga bicikla;
\bullet	početak 4. godine: zadržavanje dotad korištenoga bicikla;
\bullet	početak 5. godine: zadržavanje dotad korištenoga bicikla;
\bullet	kraj 5. godine/početak 6. godine: prodaja dotad korištenoga bicikla.

Dobivena optimalna politika uistinu je kombinacija trajanja vlasništva od jedne, odnosno tri godine, tj. navedenoj optimalnoj politici odgovara rastav 5 = 1 + 1 + 3. Vrijedi istaknuti da je ukupan broj različitih optimalnih politika jednak ukupnom broju različitih načina na koji se broj 5 može napisati kao zbroj barem jedne «jedinice» i barem jedne «trojke», a taj je jednak 3. Ti načini su: 1 + 1 + 3, 1 + 3 + 1, 3 + 1 + 1 i svaki od njih generira jednu optimalnu politiku (prvi način generira gore navedenu optimalnu politiku, drugi način generira optimalnu politiku kupnje novoga bicikla u 2. i 5. godini, a treći optimalnu politiku kupnje novoga bicikla u 4. i 5. godini). Sve tri optimalne politike daju iste minimalne ukupne neto troškove u iznosu od 640 n.j.

U prethodnim primjerima razmatrani su slučajevi u kojima je na početku prve godine već bila donesena odluka o kupnji nove opreme (automobila, bicikla), pa su se sve ostale odluke donosile na početku svake od sljedećih n godina (tu uključujemo i završnu odluku o rashodovanju opreme). Međutim, u praksi se nerijetko javljaju slučajevi u kojima na početku prve godine već raspolažemo s opremom starom i godina, čiji je vijek trajanja ukupno n godina, pa treba razmotriti optimalnu politiku zamjene u sljedećih n - i godina. I u takvim se slučajevima problem zamjene opreme može svesti na problem najkraćega puta u digrafu, no, u takvom se grafu pojavljuju negativne težine lukova i višestruki lukovi između dvaju vrhova, pa navedeni problem nije moguće riješiti uz pomoć računalnoga programa Graph Magics. Stoga će se takav problem riješiti «klasično» ilustrirajući tehniku dinamičkoga programiranja koja se ovdje primjenjuje.



Pretpostavlja se da se na početku prve godine raspolaže vozilom starim dvije godine. Vozilo je potrebno koristiti u sljedeće n = 3 godine, pri čemu se na početku svake godine (uračunavajući i prvu!) donosi odluka: zadržati postojeće vozilo još godinu dana ili rashodovati postojeće vozilo i kupiti novo. Kao i prije, godišnji trošak održavanja vozila zadan je tablično kao funkcija starosti automobila:


Nadalje, cijena novoga vozila u sve je tri godine stalna i iznosi p = 60 n.j. Likvidacijska neto vrijednost automobila starog i godina zadana je funkcijom: Treba odrediti optimalnu politiku zamjene automobila u cjelokupnom razdoblju planiranja. Ukupan broj različitih politika zamjene jednak je 2^{n} = 2^{3} = 8 jer početkom svake godine donosimo jednu od dviju mogućih odluka.

Prvi korak u rješavanju problema je definiranje funkcije optimalne vrijednosti V=V(k,i) s:
Funkcija V je funkcija dviju cjelobrojnih (točnije, prirodnih) varijabli: k i i. Varijabla k naziva se varijabla etape i ona «mjeri» razdoblja (etape) u kojima se donosi točno jedna odluka. U ovom slučaju varijabla etape poprima vrijednosti iz skupa \lbrace 1, 2, 3, 4\rbrace jer će se početkom 1., 2., 3. i 4. godine donositi odluka o zadržavanju ili rashodovanju vozila. Treba primijetiti da će početkom (n + 1)–te, tj. 4. godine biti donesena odluka o rashodovanju vozila jer će završiti planirano razdoblje u kojemu se želi koristiti vozilo. Varijabla i naziva se varijabla stanja i ona «mjeri» starost vozila na početku godine k. Ta će varijabla poprimati vrijednosti iz skupa \lbrace 1, 2, 3, 4, 5\rbrace jer najveća moguća starost vozila iznosi i_{\max} = 2 + 3 = 5 godina3.

Iz postavke navedenoga primjera slijedi da treba izračunati vrijednost V(1, 2) jer se na početku prve godine (k = 1) raspolaže vozilom starosti i = 2 godine. Navedena se vrijednost izračunava tako da se najprije definira dvoindeksna rekurzivna relacija koju zadovoljavaju vrijednosti V(k, i), a potom početni uvjeti koji omogućuju računanje konkretnih vrijednosti te funkcije.

Spomenuta dvoindeksna rekurzivna relacija dobiva se na sljedeći način: Pretpostavimo da se na početku godine k koristi vozilo staro i godina. Moguće su točno dvije alternative: A_{1}= zadržati vozilo još godinu dana i A_{2}= rashodovati vozilo i zamijeniti ga novim vozilom.

Ako se donese odluka A_{1}, tj. odluči li se zadržati vozilo i koristiti se njime u cijeloj godini k (do početka godine k + 1), ukupni neto trošak u godini k koji proizlazi iz takve odluke tvori isključivo neto trošak održavanja automobila starog i godina. Taj je trošak jednak c_{i}. Sljedeća etapa u kojoj se donosi odluka je početak (k + 1) godine, a u tom trenutku na raspolaganju će biti vozilo starosti i + 1 godina. Najmanji ukupni neto troškovi od početka (k + 1) godine do kraja razdoblja planiranja, prema definiciji funkcije V, iznose V(k + 1, i + 1). Prema tome, ukupni neto troškovi nastali kao posljedica izbora alternative A_{1} na početku godine k iznose c_{i} + V(k + 1, i + 1).

Ako se donese odluka A_{2}, tj. odluči li se rashodovati dotad korišteno vozilo i kupiti novo, u godini k pojavljuju se trošak nabave novoga vozila, godišnji trošak njegova održavanja te prihod dobiven rashodovanjem i prodajom dotadašnjega vozila, tj. prihod jednak likvidacijskoj vrijednosti dotadašnjega vozila. Trošak nabave novoga vozila jednak je njegovoj nabavnoj cijeni, tj. p. Godišnji neto trošak održavanja novoga vozila iznosi c_{0}, a likvidacijska vrijednost dotadašnjega vozila (staroga i godina) iznosi s_{i}. Stoga ukupni neto troškovi u godini k iznose p + c_{0} - s_{i}. Sljedeća etapa u kojoj se donosi odluka je početak (k + 1) godine, a u tom trenutku na raspolaganju je vozilo staro jednu godinu. Najmanji ukupni neto troškovi od početka (k + 1) godine do kraja razdoblja planiranja, prema definiciji funkcije V, iznose V(k + 1, 1). Prema tome, ukupni neto troškovi nastali kao posljedica izbora alternative A_{2} na početku godine k iznose p + c_{0} - s_{i} + V(k + 1, 1).

Budući da ukupne neto troškove treba minimizirati u svakoj pojedinoj etapi, iz navedenih razmatranja proizlazi sljedeća jednakost: Navedena jednakost je tražena dvoindeksna rekurzivna relacija uz pomoć koje se računaju vrijednosti funkcije V. Preostaje zadati početne uvjete, tj. neke vrijednosti funkcije V uz pomoć kojih se može izračunati svaka od preostalih vrijednosti te funkcije.

Da bi se mogli zadati početni uvjeti, razmatra se odluka koja se donosi na kraju razdoblja planiranja, odnosno početkom četvrte godine. Pripadna vrijednost varijable etape je k = 4, pa se zapravo zadaju vrijednosti V(4, i). Na kraju razdoblja planiranja moguća je točno jedna odluka: rashodovati dotad korišteno vozilo. To vozilo ne može biti novo, tj. ne može biti i_{\min} = 0, pa je najmanja moguća starost vozila jednaka i = 1. Najveća moguća starost vozila jest i = 5, pa se računaju vrijednosti V(4, i) za i = 1, 2, 3, 4, 5. Rezultat odluke rashodovati dotad korišteno vozilo je prihod jednak likvidacijskoj vrijednosti vozila na početku četvrte godine. Budući da minimiziramo ukupne troškove, prihod se formalno evidentira kao negativni trošak:
Zadavanjem navedenih vrijednosti moguće je izračunati svaku od preostalih vrijednosti funkcije V na temelju prethodno navedene rekurzivne relacije. Najprije se razmatra početak treće godine, odnosno etapa k = 3. Najveća moguća starost vozila u toj etapi je i = 4, pa se računaju vrijednosti V(3, i), za i = 1, 2, 3, 4:
U sljedećoj fazi razmatra se početak druge godine, odnosno etapa k = 2. Najveća moguća starost vozila u toj etapi je i = 3, pa se računaju vrijednosti V(2, i), za i = 1, 2, 3:
U sljedećoj fazi razmatra se početak prve godine, odnosno etapa k = 1. Najveća moguća starost vozila u toj etapi je i = 2, pa se radi potpunosti računaju vrijednosti V(1, i), za i = 1, 2:
Vrijednost V(1, 2) jednaka je 105, pa slijedi da ukupni minimalni troškovi korištenja vozila u razdoblju planiranja iznose 105 n.j. Vrijedi istaknuti da se ta vrijednost postiže i izborom alternative A_{1} i izborom alternative A_{2}, što znači da postoje ukupno dvije različite optimalne politike zamjene. Te se politike mogu lako «očitati» iz gore provedenih izračuna na sljedeći način:


1. optimalna politika zamjene

\bullet	početak 1. godine: zadržati vozilo staro dvije godine;
\bullet	početak 2. godine: vrijednost V(1, 2) = 105 u ovom je slučaju dobivena uz pomoć vrijednosti V(2, 3) = 65. Ta je vrijednost dobivena izborom alternative A_{2} na početku 2. godine, što znači da tada treba rashodovati dotad korišteno vozilo i kupiti novo;
\bullet	početak 3. godine: vrijednost V(2, 3) = 65 dobivena je uz pomoć vrijednosti V(3, 1) = 5. Ta je vrijednost dobivena izborom alternative A_{1} na početku 3. godine, što znači da tada treba zadržati dotad korišteno vozilo;
\bullet	početak 4. godine: rashodovati dotad korišteno vozilo.

2. optimalna politika zamjene

\bullet	početak 1. godine: rashodovati vozilo staro 2 godine i kupiti novo;
\bullet	početak 2. godine: vrijednost V(1, 2) = 105 u ovom je slučaju dobivena uz pomoć vrijednosti V(2, 1) = 50. Ta vrijednost dobivena je izborom alternative A_{1} na početku 2. godine, što znači da tada treba zadržati dotad korišteno vozilo;
\bullet	početak 3. godine: vrijednost V(2, 1) = 50 dobivena je uz pomoć vrijednosti V(3, 2) = 30. Ta je vrijednost dobivena izborom alternative A_{1} na početku 3. godine, što znači da tada treba zadržati dotad korišteno vozilo;
\bullet	početak 4. godine: rashodovati dotad korišteno vozilo.

U prethodnim su se primjerima nastojali minimizirati ukupni troškovi nastali korištenjem opreme. No, u praksi se vrlo često javljaju i problemi maksimizacije ukupne dobiti nastale korištenjem neke opreme. Postupak rješavanja takvih problema bit će ilustriran na sljedećim primjerima.



Za opremu nekoga proizvodnog pogona koja osigurava nesmetan i neprekidan proces proizvodnje zadane su nabavna cijena p = 120 n.j. i funkcija neto dobiti, nastale korištenjem opreme (d). Nakon određenoga vremena korištenja opremu nije moguće prodati, pa početkom svake godine treba donijeti odluku o zamjeni ili zadržavanju dotadašnje opreme. Godišnja neto dobit od korištenja opreme zadana je kao funkcija starosti opreme (i): Treba odrediti optimalnu politiku zamjene opreme u razdoblju od n = 8 godina ako se na početku prve godine raspolaže opremom starom tri godine.

Analogno kao u prethodnom primjeru definira se realna funkcija V dviju cjelobrojnih varijabli s: Budući da se na početku prve godine raspolaže opremom starom 3 godine, treba izračunati vrijednost V(1, 3). U tu svrhu najprije se određuje odgovarajuća dvoindeksna rekurzivna relacija i zadaju početni uvjeti.

Za određivanje rekurzivne relacije provodi se sljedeće zaključivanje: Pretpostavlja se da se na početku godine k koristi oprema stara i godina. Odluka na početku te godine je točno jedna od alternativa A_{1} = zadržati opremu još godinu dana i A_{2}= zamijeniti dotad korištenu opremu.

Ako se donese odluka A_{1}, tj. odluči li se zadržati opremu i koristiti se njome u cijeloj godini k (do početka godine k + 1), ukupna neto dobit u godini k koja proizlazi iz takve odluke jednaka je neto dobiti nastaloj korištenjem opreme stare i godina. Ta je neto dobit jednaka d_{i}. Sljedeća etapa u kojoj se donosi odluka je početak (k + 1) godine, a u tom trenutku raspolaže se opremom starom i + 1 godina. Najveća ukupna neto dobit od početka (k + 1) godine do kraja razdoblja planiranja, prema definiciji funkcije V, iznosi V(k + 1, i + 1). Prema tome, ukupna neto dobit nastala kao posljedica izbora alternative A_{1} na početku godine k iznosi d_{i} + V(k + 1, i + 1).

Ako se donese odluka A_{2}, tj. odluči li se zamijeniti oprema, u godini k pojavit će se trošak nabave nove opreme i neto dobit nastala korištenjem nove opreme. Trošak nabave nove opreme jednak je nabavnoj cijeni opreme, tj. p. Godišnja neto dobit nastala korištenjem nove opreme iznosi d_{0}. Stoga ukupna neto dobit u godini k iznosi d_{0} - p. Sljedeća etapa u kojoj se donosi odluka je početak (k + 1) godine, a u tom trenutku raspolaže se opremom starom jednu godinu. Najveća ukupna neto dobit od početka (k + 1) godine do kraja razdoblja planiranja, prema definiciji funkcije V, iznosi V(k + 1, 1). Prema tome, ukupna neto dobit nastala kao posljedica izbora alternative A_{2} na početku godine k iznosi d_{0} - p + V(k + 1, 1).

Budući da ukupnu neto dobit treba maksimizirati u svakoj pojedinoj etapi, iz navedenih razmatranja proizlazi sljedeća jednakost:
Preostaje zadati početne uvjete. U tu se svrhu razmatra odluka koja se donosi početkom posljednje godine razdoblja planiranja, odnosno početkom osme godine. Pripadna vrijednost varijable etape je k = 8, pa se zapravo zadaju vrijednosti V(8, i). Najmanja moguća vrijednost varijable stanja je i_{\min} = 0 i postiže se ako se početkom 8. godine donese odluka o kupnji nove opreme. Najveća moguća vrijednost varijable stanja jednaka je i_{\max} = 3 + 7 = 10 i postiže se ako se oprema stara 3 godine zadrži tijekom svih osam godina. Budući da, prema definiciji funkcije V, za svaki k = 9, 10, 11, \ldots i svaki i \in \mathbb{N} vrijedi jednakost: izraz za izračunavanje vrijednosti V(8, i) može se transformirati ovako: Dobiva se:


U sljedećoj fazi računaju se vrijednosti V(7, i). U etapi k = 7, tj. početkom 7. godine najveća moguća vrijednost varijable stanja je i_{\max} = 3 + 6 = 9, pa se računaju vrijednosti V(7, i) za i = 0, 1, 2, \ldots, 8, 9. Koristeći se navedenom dvoindeksnom rekurzivnom relacijom, dobiva se: (što znači da ako se početkom sedme godine raspolaže opremom starom barem 3 godine, svakako se isplati kupiti novu).
Analogno se postupa u svakoj od sljedećih šest faza. Dobivaju se sljedeće vrijednosti: (što znači da ako se početkom šeste godine raspolaže opremom starom barem dvije godine, svakako se isplati kupiti novu); (što znači da ako se početkom pete godine raspolaže opremom starom barem tri godine, svakako se isplati kupiti novu); (što znači da ako se početkom četvrte godine raspolaže opremom starom barem četiri godine, svakako se isplati kupiti novu); (što znači da ako se početkom treće godine raspolaže opremom starom barem tri godine, svakako se isplati kupiti novu); (što znači da ako se početkom druge godine raspolaže opremom starom barem tri godine, svakako se isplati kupiti novu); Prema tome, tražena maksimalna ukupna neto dobit u cjelokupnom razdoblju planiranja iznosi 480 n.j. Preostaje odrediti optimalnu politiku zamjene opreme, odnosno «očitati» slijed odluka. Vrijednost V(1, 3) = 480 postiže se neovisno o izboru alternative (A_{1} ili A_{2}). Stoga se dobivaju sljedeće optimalne politike:


1. optimalna politika

\bullet	početak 1. godine: zadržati postojeću opremu;
\bullet	početak 2. godine: zamjena opreme;
\bullet	početak 3., početak 4. i početak 5. godine: zadržati postojeću opremu;
\bullet	početak 6. godine: zamjena opreme;
\bullet	početak 7. i početak 8. godine: zadržati postojeću opremu.

2. optimalna politika

\bullet	početak 1. godine: zadržati postojeću opremu;
\bullet	početak 2. godine: zamjena opreme;
\bullet	početak 3. i početak 4. godine: zadržati postojeću opremu;
\bullet	početak 5. godine: zamjena opreme;
\bullet	početak 6., početak 7. i početak 8. godine: zadržati postojeću opremu.

3. optimalna politika

\bullet	početak 1. godine: zamjena opreme;
\bullet	početak 2., početak 3. i početak 4. godine: zadržati postojeću opremu;
\bullet	početak 5. godine: zamjena opreme;
\bullet	početak 6., početak 7. i početak 8. godine: zadržati postojeću opremu.

Ako se unaprijed donese odluka da se na početku prve godine zamjenjuje dotad korištena oprema, postupak donošenja optimalne politike zamjene može se svesti na određivanje kritičnoga puta u težinskom digrafu. Navedeno je modeliranje moguće ako i samo ako je težina svakoga luka (i, j) za i \lt j pozitivan realan broj4. Postupak se prikazuje na sljedećem primjeru.



Treba riješiti primjer 4 uz dodatan uvjet da se početkom prve godine obavezno nabavlja nova oprema. Odmah se može uočiti da će rješenje ovoga primjera biti 3. optimalna politika iz primjera 4.

Matematički model je potpuni težinski digraf čiji vrhovi označuju početke godina. Budući da je razdoblje planiranja dugo n = 8 godina, digraf će imati ukupno n + 1 = 8 + 1 = 9 vrhova: 1, 2, 3, 4, 5, 6, 7, 8, 9 (vrh 9 interpretiramo kao kraj 8. godine, odnosno kraj razdoblja planiranja). Vrhovi i i j bit će spojeni lukom od i prema j ako i samo ako je i \lt j, pa će graf imati ukupno \binom{9}{2} = 36 različitih lukova. Preostaje zadati težinu svakoga luka:
Budući da je d_{0} = p = 120 n.j, ukupna neto dobit u prvoj godini korištenja opreme jednaka je 0, pa za svaki i = 1, 2, 3, 4, 5, 6, 7, 8 vrijede jednakosti: Prema definiciji veličina d_{i}, za svaki i \in \mathbb{N} očito vrijedi nejednakost d_{i} \geq 0, pa je nužan uvjet za modeliranje problema potpunim težinskim digrafom ispunjen. Nadalje, zbog slijedi:
Uz pomoć računalnoga programa Grin dobiva se digraf prikazan na slici 3.
Primjenom procedure Critical Path implementirane u istom računalnom programu određuje se kritični put u tom digrafu:


Njegova je težina 480 i ona je jednaka optimalnoj ukupnoj neto dobiti. Jedini unutrašnji vrh u kritičnom putu je vrh 5, pa slijedi da početkom 5. godine treba zamijeniti dotadašnju opremu. Kad se tomu doda unaprijed postavljeni uvjet da se početkom prve godine obavezno kupuje nova oprema, dobiva se 3. optimalna politika dobivena u rješenju primjera 4.

Zaključno se može istaknuti kako se još neki tipovi logističkih problema također mogu riješiti uz pomoć modela i algoritama teorije grafova (vidjeti [4]).

Riječ logistika često se javlja u suvremenim masovnim medijima, npr. novinama i časopisima. Što je logistika? Logistika je upravljanje protokom roba, informacija i drugih resursa, uključujući energiju i ljude, između točke izvora (ishodišta) i točke konzumacije (potrošnje) s ciljem udovoljavanja zahtjevima potrošača (često, i izvorno, vojnim organizacijama). Logistika uključuje integraciju informacija, transporta, popisivanja, skladištenja, baratanja i pakiranja.

Postoji mnogo logističkih problema u svakodnevnom životu. Na primjer: dostava pošte, skupljanje otpada, čišćenje snijega, posipanje ulica solju zimi, čišćenje ulica, održavanje puteva, određivanje ruta školskih autobusa i mnogi drugi. Održavanje putova zimi zahtijeva mnogo složenog strateškog i operativnog planiranja. Glavni problemi uključuju pozicioniranje skladišta, označivanje sektora, određivanje ruta servisnih vozila, određivanje voznog reda. Čišćenje snijega i posipanje puteva zimi vrlo je bitna a i skupa usluga. Ako ceste nisu očišćene na vrijeme, ili zaleđeni putevi nisu posuti solju, mnogo sudionika u prometu izvrgnuto je većoj pogibelji, a o nezadovoljstvu građana da ne govorimo. Optimiranje čišćenja snijega i posipanja ulica solju treba izvesti pazeći na dva aspekta: sigurnost i ekonomičnost. Sigurnosni aspekti zahtijevaju da najosjetljivije točke mreže (ona mjesta koja se lede prva) budu očišćena prva. Ekonomičnost zahtijeva da ruta čišćenja bude najjeftinija. Svi ovi problemi mogu biti riješeni koristimo li algoritme teorije grafova.

U matematici i računarstvu pod teorijom grafova smatra se proučavanje grafova, matematičkih struktura korištenih da bi se predstavile relacije koje uključuju dva elementa određene kolekcije. Neformalno govoreći, graf je skup objekata zvanih vrhovi, točke ili čvorovi povezanih vezama zvanima bridovi ili linije. Ako je dan skup čvorova i drugi skup objekata zvanih bridovi, graf je definiran kao odnos između tih skupova: svaki brid spaja par čvorova. Grafovi se prikazuju crtanjem točaka za svaki vrh i povlačenjem luka između dvaju vrhova, ako su oni povezani bridom. Ako je graf usmjeren, smjer se navodi crtanjem strelice.

Svakom bridu možemo pridružiti realan broj, što znači da je graf proširen težinskom funkcijom. U slučaju kada graf predstavlja mrežu cesta, težinska funkcija je npr. duljina svakog puta. Takav se graf zove težinski graf.

Teorija grafova ima široke primjene u različitim disciplinama. U teoriji grafova razmatramo strukure s pomoću kojih možemo modelirati mnogo problema iz svakidašnjeg života. Začetak teorije grafova možemo povezati s jednim problemom iz realnog života, koji bi se u današnje vrijeme nazvao logističkim problemom. Taj problem postavio je i riješio 1736. eminentni švicarski matematičar Leonhard Euler. Nekoliko godina poslije Euler je izdao članak Solutio problematis ad geometriam situs pertinentis u časopisu Commentarii academiae scientiarum Petropolitanae, u kojem je formulirao i riješio problem Sedam königsberških mostova. Ovaj rad, objavljen 1741., danas se smatra prvim radom u matematičkoj disciplini teoriji grafova.


Graf G matematička je struktura koja se koristi za opisivanje relacija između dvaju objekata iz određene kolekcije. U ovom kontekstu graf se odnosi na neprazni skup vrhova i kolekciju bridova koji povezuju par vrhova. Skup vrhova obično se označava s V(G), a skup bridova s E(G). Bridovi mogu biti usmjereni ili ne, ovisno o primjeru. Graf kojemu su svi bridovi usmjereni zovemo usmjerni graf, u suprotnom, zovemo ga neusmjereni. U pravom grafu, za koji inicijalno pretpostavljamo da je neusmjeren, linija od točke u do točke v identificira se s linijom od točke v do točke u. U digrafu (skraćeno za usmjereni graf), ta dva smjera smatraju se različitim lukovima, odnosno bridovima. Ako graf G nije usmjeren, tada su dva vrha pridružena jednom bridu međusobno ravnopravna. U usmjerenom grafu brid može biti usmjeren od jednog vrha orema drugome. Slike 1 i 2 primjeri su usmjerenih grafova.

Brid koji počinje i završava u istom vrhu zove se petlja. Brid je višestruk ako postoji drugi brid kojemu odgovaraju isti vrhovi (kao početni i krajnji vrh). (Slika 3).

Graf se naziva jednostavnim ako je neusmjeren, nema petlji i između bilo koja dva vrha nema više od jednog brida. U jednostavnom grafu svaki se brid može identificirati s parom različitih vrhova. Brid povezuje dva vrha. Ta dva vrha nazivaju se incidentnima tom bridu, odnosno brid je incidentan tim dvama vrhovima. Stupanj vrha v u grafu G je broj bridova koji su incidentni s v, pri čemu se petlje broje dva puta. Slika 4 pokazuje da su bridovi vu, vt , vw incidentni vrhu v. Prema tome, stupanj vrha v je 3.

Ako je skup bridova E(G) konačan, tada je ukupna suma stupnjeva svih bridova jednaka dvostrukom broju bridova. Vrhovi u i v su susjedni ako postoji brid između njih.

Neka je G graf sa skupom vrhova V(G) i skupom bridova E(G) i neka je G' graf sa skupom vrhova V(G') i skupom bridova E(G'). Tada je G' podgraf grafa G ako je V(G') podskup od V(G) i E(G') podskup od E(G). Podgraf G' je razapinjući podgraf grafa G ako ima isti skup vrhova kao i G. Na Slici 5 vidimo graf (na lijevoj strani) i njegov podgraf (na desnoj strani).



Šetnja je alternirajući niz vrhova i bridova, koji počinje i završava vrhom, u kojem je svaki vrh incidentan bridu koji mu prethodi i bridu koji mu slijedi u tom nizu, a vrh koji prethodi bridu i vrh koji slijedi taj brid krajnji su vrhovi tog brida. Niz od i bridova v_{0}v_{1}, v_{1}v_{2}, \ldots, v_{i-1}v_{i} u grafu G šetnja je od vrha v_{0} do vrha v_{i} duljine i u G. Šetnju obično označavamo s v_{0}v_{1}v_{1}v_{2}\ldots v_{i-1}v_{i}. Šetnja je zatvorena ako su joj prvi i zadnji vrh jedanki, a otvorena ako su različiti. Ako u otvorenoj šetnji nema ponavljanja vrhova (pa prema tome ni bridova), zovemo je put. Slika 6 daje primjer puta.

Staza je šetnja u kojoj su svi bridovi međusobno različiti. Zatvorena staza zove se tura. Staza je Eulerova ako se u njoj pojavljuju svi bridovi u grafu, i to točno jedanput. Udaljenost između vrhova v_{0} i v_{i} u grafu G je duljina najkraćeg puta među njima, tj. broj bridova kojima se on koristi. Udaljenost između vrhova v_{0} i v_{i} označavamo s d_{G}(u_{0},v_{i}) (Slika 7).

Za graf kažemo da je povezan ako postoji put između bilo koja dva vrha u grafu. U suprotnom, graf zovemo nepovezanim. Slika 8 pokazuje nam primjer povezanog i nepovezanog grafa.

Graf se naziva stablom ako su svaka dva vrha u njemu povezana točno jednim putem. Ciklus je zatvorena staza u kojoj su svi unutarnji vrhovi međusobno različiti. Svaki povezani graf bez ciklusa je stablo.

Neka je G povezan, neusmjeren graf. Razapinjuće stablo u tom grafu je podgraf koji je stablo i razapinje taj graf. Jedan graf može imati mnogo razapinjućih stabala. U težinskom grafu minimalnim razapinjućim stablom zovemo ono stablo čija je težina (tj. suma težina njegovih bridova) manja ili jednaka težini svakog drugog razapinjućeg stabla (Slika 9).



U ovoj sekciji predstavljamo problem Sedam königsberških mostova. Grad Königsberg (Kaliningrad, adminsirativni dio Rusije, ali zemljopisno između Poljske i Litve) leži na obalama rijeke Pregel. Kao što se vidi na Slici 10, na rijeci se nalaze dva veća otoka koja su međusobno i s obalama povezani s pomoću sedam mostova. Euler je postavio sljedeći problem:


Postoji li šetnja preko svih sedam mostova koji povezuju dva otoka na rijeci Pregel s ostakom grada Königsberga takva da se svaki most prijeđe točno jedanput?

Kao što je Euler pokazao u članku, takva šetnja ne postoji.



Dolazimo do pitanja: zašto Eulerova šetnja? Put koji prolazi kroz svaku spojnicu (brid) samo jednom zove se Eulerova šetnja jer je upravo Euler razriješio pitanje

königsberških mostova, koje je sadržavalo zahtjev da se svaki brid prijeđe samo jednom.

Na Slici 10 kako je Königsberg izgledao u to vrijeme. Kao što vidimo, četiri dijela grada (sjeverni, južni i dva otoka) bila su međusobno povezana putem sedam mostova. Manji otok s po dva je mosta povezan sa sjevernim i s južnim dijelom grada. Veći otok s po jednim je mostom povezan sa sjevernim s južnim dijelom grada, a postojao je i jedan most koji je povezivao dva otoka.

Dok je proučavao problem, Euler je došao na genijalnu ideju da različite dijelove grada označi vrhovima, a mostove među njima bridovima. Na taj je način konstruirao graf s četiri vrha i sedam bridova, kao što možemo vidjeti na Slici 11.

Na taj je način modelirao Königsberg i njegove mostove koristeći se teorijom grafova (u to vrijeme pojam još nije postojao). Detaljno proučavajući taj problem, Euler je došao do zaključka da rješenje ne postoji. Nekoliko stoljeća poslije znamo da se zatvorena Eulerova šetnja može naći samo u grafovima u kojima je stupanj svakog vrha paran. Prema tome se grafovi u kojima su svi vrhovi parnog stupnja nazivaju Eulerovim.

Kao što smo spomenuli na početku, teorija grafova vrlo je primjeren alat za rješavanje logističkih problema. Izdvojimo neke od problema koji su riješeni uz pomoć teorije grafova i koji su primjenjivi na modeliranje nekih logističkih problema iz svakodnevnog života:

Problem kineskog poštara primjer je u kojem pokušavamo naći šetnju kojom prolazimo kroz svaki brid na grafu samo jednom, i to učiniti na najkraći mogući način, koristeći se usmjerenim ili neusmjerenim grafom. Za bolje razumijevanje možemo zamisliti poštara koji hoda ulicama (u našem slučaju po grafu) i koji želi uručiti poštu u svaku kuću (vrhovi našeg grafa) u najkraćem veremenu i tada se vratiti u poštu (polaznu točku). Poštar nastoji uštedjeti vrijeme, trud i novac izvršavajući svoj zadatak tako da upotrijebi najkraću rutu.

Problem trgovačkog putnika na je prvi pogled vrlo sličan problemu kineskog poštara. Bavi se slučajem u kojem tražimo šetnju u usmjerenom ili neusmjerenom grafu tako da prođemo svaki vrh u grafu barem jednom i vratimo se u početni vrh na najkraći mogući način. Možemo zamisliti da su pri tome i zadane udaljenosti među vrhovima, pa tražimo da je i ukupna prijeđena udaljenost najmanja.

U potrazi za najkraćim putem želimo naći najkraći put (npr. u težinskom grafu) između nekih dvaju vrhova.

Konačno, možemo reći da se rješavanje gore spomenutih problema vrlo lijepo uklapa u rješavanje logističkih problema iz svakidašnjeg života. Naprimjer:

\bullet	Putevi ralica za snijeg mogu biti modelirani uz pomoć teorije grafova. Za tu priliku koristimo neku varijaciju problema kineskog poštara
\bullet	Konstrukcija kabelske ili električne mreže, cjevovoda za vodovod i sl., može biti riješena potragom za minimalnim razapinjućim stablom
\bullet	Rute i redoslijed transporta robe od skladišta do trgovina mogu se modelirati preko problema trgovačkog putnika
\bullet	Planiranje fiksne telefonske mreže koja povezuje nekoliko različitih objekata modelirano je preko potrage za minimalnim razapinjućim stablom
\bullet	Potraga za najkraćim putem vrlo je raširena u svakodnevnom životu. Popularna GPS tehnologija može se vidjeti u mnogim motornim vozilima kao metoda za pronalaženje pravog puta od jedne do druge točke na zemljopisnoj karti.

Rezultati teorije grafova vrlo su korisni ljudima koji rješavaju logističke probleme. Zapravo, možemo reći da su ti rezultati esencijalni za njihovo rješavanje. Prema jednoj od mnogih definicija, logistički zadatak je, među ostalim, osigurati da su zadovoljavajuće količine robe dostupne primateljima i da u pravo vrijeme budu na pravom mjestu. Postoji mnogo svakodnevnih logističkih problema (vojno-logističkih, upravljačkih, poslovno-logističkih, proizvodno-logističkih i ostalih) koji mogu biti riješeni primjenom teorije grafova. Naprimjer, praktična primjena Problema kineskog poštara je planiranje ruta autobusnog javnog prijevoza. Da bi uštedjela na gorivu, autobusna kompanija može modelirati autobusnu stanicu kao vrh i cestu kao brid u ruti autobusa, te koristeći se teorijom grafova pronaći optimalnu rutu koja može udovoljiti cilju minimiziranja potrošnje goriva, ali uz uvjet da se svaka zadana cesta prijeđe barem jednom. Ostale primjene uključuju skupljanje smeća, čišćenje ulica, čišćenje snijega, šišanje trave oko autoputa, ispitivanje dalekovoda, određivanje ruta školskih autobusa itd.