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.