teorija grafova

Broj 42

Poštovani čitatelji-

 

U postupku je izdavanje 42 broja časopisa. U ovom broju vam donosimo članke

  1. O nekim metodičkim problemima u obradi standardizacije normalne slučajne varijable,  autora Mandi Orlić Bachler i Bojan Kovačića. 
  2. Sokoban je NP–težak autora Stjepana Požgaja i Mladena Vukovića
  3. Turanov teorem, autora Snježane Majstorović i Mateja Rechnera

 

Želimo vam ugodno čitanje.

 

Srdaćan pozdrav, L. Grubišić.

27. broj časopisa e.math

Dragi čitatelji,

izašao je 27 broj časopisa e.math.

U ovom broju donosimo vam članke vezane uz teoriju grafova, heurističku optimizaciju i genetske algoritme te metodički članak o nastavnom pristupu čunjosječnicama.

U članku Genetski algoritmi i biomorfi, autora Tomislava Droždjeka i Nele Bosner daje se prikaz evolucijskih algoritama kao vrste heurističkih optimizacijskih algoritama koji su projektirani oponašanjem prirodnih procesa (u ovom slučaju procesom evolucije). Istaknimo da je po rječničkoj definiciji heuristički postupak onaj u kojem se znanstveno rješenje traži metodom pokušaja i pogrešaka. U slučaju optimizacije to znači da nećemo rigorozno dokazivati da je pronađeno rješenje (izlaz iz algoritma) optimalno, već ćemo se zadovoljiti time da izlaz iz algoritma ima bolja svojstva (mjera kojih je funkcija cilja) od ulaza (početnog stanja) u algoritam. Evolucijski algoritmi su područje istraživanja računarstva, a ovaj članak može služiti kao izvrsna referenca studentima matematike i računarstva za kolegij Umjetna inteligencija.  Pdf verziju članka možete naći na portalu Hrcak.

U članku Petersenov graf, autora Snježane Majstorović i Luke Borasa daje se pregled rezultata vezanih uz Petersonov graf. To je graf s 10 vrhova i 15 bridova koji se pojavljuje kao čest protuprimjer za mnoge probleme u teoriji grafova. Jedno od zanimljivih svojstava Petersonovog grafa je da je to najmanji snark. Istaknimo da je 1946 Danilo Blanuša pronašao dva snarka s 18 vrhova koji su danas poznati kao blanušini snarkovi jedan od kojih je i logo Hrvatskog matematičkog društva.  Pdf verziju članka možete naći na portalu Hrčak.

U članku Različiti nastavno-metodički pristupi čunjosječnicama, Ivančice Mirošević, Nikole Koceić-Bilana i Josipe Jurko dan je pregled različitih metodičkih pristupa uvođenju čunjosječnica u nastavu matematike. Članak stavlja naglasak na metodičku vrijednost geometrijskog pristupa konstrukciji i uvođenju čunjosječnica u nastavi matematike. Trenutna metodička praksa gotovo isključico stavlja nastavak na algebarski pristup, čime se propušta prilika senzibiliziranja učenika za otkrivanje i povezivanje svojstava geometrijskih objekata s pojavama koje ga okružuju (npr. korištenje i značaj krivulja drugog reda u arhitekturi, optici ili astronomiji). Vezano uz primjene svojstava krivulja drugog reda u astronomiji istaknimo i Papus-Boškovićev pristup krivuljama drugog reda i s time povezan pojam numeričkog ekscentriciteta elipse. Pdf verziju članka možete naći na portalu Hrčak.

U ime uredništva želim vam ugodno čitanje.

L. Grubišić
glavni urednik

Od koenigsberških mostova do kineskog poštara

 
Anka Golemac, Ana Mimica i Tanja Vučičić
Prirodoslovno-matematički fakultet Sveučilišta u Splitu
golemac@pmfst.hr

2012

Od koenigsberških mostova do kineskog poštara

Sažetak
U članku se daje kratak osvrt na povijest teorije grafova i u tom kontekstu govori o rješavanju Problema kineskog poštara kao jednog o najpoznatijih problema kombinatorne optimizacije.
 

1Što bilježe kroničari

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.


Slika 1: Koenigsberški mostovi


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. 


Slika 2: Shematski prikaz


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.

2Malo o grafovima

Definicija 1. Graf  je uređena trojka G=(V,E,\varphi), gdje je V=V\left( G\right) neprazan skup čije elemente nazivamo vrhovima, E=E\left( G\right) je skup disjunktan s V čije elemente nazivamo bridovima i \varphi je funkcija koja svakom bridu e iz E pridružuje par \left\lbrace u,v\right\rbrace, ne nužno različitih vrhova iz V. Graf skraćeno označavamo G=(V,E) ili samo G.


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.

Teorem 2. Povezani graf je Eulerov ako i samo ako mu je svaki vrh parnog stupnja. Povezani graf koji nije Eulerov sadržava Eulerovu stazu ako i samo ako ima točno dva vrha neparnog stupnja.


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.

Definicija 3. Digraf ili usmjereni graf D je uređena trojka D=\left( V,A,\psi\right), gdje je V=V\left( D\right) neprazan skup čije elemente nazivamo vrhovima, A=A\left( D\right) skup disjunktan s V čije elemente nazivamo lukovima i \psi funkcija koja svakom luku a iz A pridružuje uređeni par (u,v), pri čemu u,v\in V nisu nužno različiti. Kažemo da je u početak, a v kraj luka a, da je smjer ili orijentacija luka a od u prema v i koristimo oznaku a=(u,v). Digraf skraćeno označavamo D\left( V,A\right) ili samo D.


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.

Teorem 4. Povezani digraf je Eulerov ako i samo ako je za svaki njegov vrh ulazni stupanj jednak izlaznom.


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].

3Traženje rješenja za CPP


Slika 3: Poštarova tura


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.

Definicija 5. Težinski graf je uređeni par \left( G,\omega\right), gdje je G graf i \omega:E\left( G\right) \rightarrow \mathbb{R} _{0}^{+} funkcija koja svakom bridu e iz G pridružuje nenegativni broj \omega\left( e\right). Vrijednost\ \omega\left( e\right) nazivamo težinom brida e.


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

Definicija 6. Poštarova tura u grafu G je zatvorena šetnja koja uključuje svaki brid grafa G najmanje jednom. U težinskom grafu optimalna poštarova tura je poštarova tura kojoj je ukupna težina uključenih bridova minimalna.


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.   

4Varijacije problema  

Kao što je rečeno, osnovni oblik CPP-a svodi se na traženje optimalne poštarove ture u težinskom grafu. Pokazalo se da uz određene modifikacije ovaj model može postati način rješavanja velikog broja vrlo različitih optimizacijskih problema, o čemu govore brojne publikacije. Spomenut ćemo za ilustraciju [4][9], [11] i [12].

Primjer 7. Poznati primjer primjene CPP-a je optimizacija rute za čišćenje ulica grada New Yorka, [2, 3]. Pretpostavimo da usmjereni graf na Slici 4 predstavlja mrežu jednosmjernih ulica. Težine lukova znače vrijeme potrebno za prolazak ulicom bez čišćenja. Lukovi su bojenjem podijeljeni u dvije klase; jedna boja (crvena) označava ulice koje treba očistiti, a druga ulice koje se mogu koristiti za prolazak. Zadatak je odrediti koja ruta minimizira ukupno vrijeme potrebno za čišćenje zadanih ulica, na način da se krene iz vrha z i završi u vrhu z


Slika 4: Usmjereni graf

 


Za primjer smo mogli uzeti slučaj u kojemu se pojavljuju i jednosmjerne i dvosmjerne ulice. To upućuje na model koji će istovremeno imati bridove i lukove.

Definicija 8. Mješoviti graf je uređena trojka M=\left( V,E,A\right), gdje je V skup vrhova, E skup bridova i A skup lukova.


S vremenom su, kroz primjene, nastale brojne verzije CPP-a vezane uz različite optimizacijske probleme. Glavne verzije su određene tipom modela. Neusmjereni CPP (UCPP-Undirected Chinese Postman Problem) za model ima težinski graf, usmjereni CPP (DCPP-Directed Chinese Postman Problem) modelira se u digraf, kao u Primjeru 7, a mješoviti CPP (MCPP-Mixed Chinese Postman Problem) za rješavanje upotrebljava mješoviti graf. Za svaku od ovih verzija postoje razne varijacije. Navodimo neke od njih, [9].

Problem ruralnog poštara (CRPP-Rural Postman Problem) je varijacija UCPP-a u kojoj se razmatra povezani težinski graf G=\left( V,E\right) s podskupom E^{\prime}\subseteq E istaknutih bridova. Cilj je pronaći zatvorenu šetnju u G najmanje težine koja svaki brid e\in E^{\prime} prijeđe barem jednom. Ime problema dolazi iz prakse dostave pošte u ruralnim sredinama gdje postoje ulice u kojima nijedan stanovnik tog dana nema pošte, ali te ulice ipak mogu služiti kao poveznice među ulicama u koje tog dana treba dostaviti poštu.

Vjetroviti CPP (WPP-Windy Postman Problem) razmatra povezani težinski graf G=\left( V,E\right) sa zadanim dvjema težinskim funkcijama. Težine svakog pojedinog brida mogu se razlikovati ovisno o smjeru prelaska brida ("s vjetrom u leđa" ili "protiv vjetra"). Cilj je pronaći zatvorenu šetnju u G najmanje težine koja svaki brid e\in E sadržava barem jedanput.

Generalizirani CPP (GCPP-Generalized Chinese Postman Problem) modelira se u povezani težinski graf G=\left( V,E\right) čiji je skup bridova E podijeljen u podskupove E_{1},...,E_{k}. Potrebno je pronaći zatvorenu šetnju najmanje težine koja sadržava barem jedan brid iz svakog od podskupova E_{1},...,E_{k}.

Mješoviti k-CPP (M k-CPP-Mixed k-Chinese Postman Problem) polazi od jako povezanog mješovitog težinskog grafa G=\left( V,E,A\right) s istaknutim vrhom i zadanim brojem k\gt 1. Cilj je pronaći skup od k mješovitih zatvorenih šetnji minimalne ukupne težine koje zadovoljavaju sljedeće uvjete:

(a)  svaka šetnja počinje i završava u istaknutom vrhu;

(b)  svaki brid sadržan je u barem jednoj šetnji.

Min-max k-CPP (MM k-CPP-Min-Max k-Chinese Postman Problem) kao polazište ima povezani težinski graf G=\left( V,E\right) s istaknutim vrhom i zadanim brojem k\gt 1. Promatraju se svi skupovi od k zatvorenih šetnji koje zadovoljavaju uvjete (a) i (b). Među njima treba pronaći skup koji ima minimalnu težinu najteže šetnje.

Hijerarhijski CPP (HCPP-Hierarchical Chinese Postman Problem) razmatra povezan težinski graf G=\left( V,E\right) čiji je skup bridova E podijeljen u nekoliko klasa između kojih je uspostavljen odnos prednosti. Ako klasa E_{p} ima veću prednost od klase E_{q}, onda bridovi iz E_{p} moraju biti prijeđeni prije onih iz E_{q}. U tom grafu treba pronaći zatvorenu šetnju minimalne težine koja prelazi svaki brid barem jedanput, tako da se poštuje odnos prednosti klasa.

Primjenjivost CPP-a u praksi, uključujući i područja visoko komercijalnih modernih tehnologija, potiče potragu za učinkovitim algoritmima i programskim alatima za njegovo rješavanje [1, 4, 10, 15]. Usmjereni CPP složeniji je od neusmjerenog, ali u osnovnoj verziji oba spadaju u probleme koji se rješavaju algoritmima polinomijalne složenosti. Mješoviti CPP još je zahtjevniji i pripada klasi NP-teških problema. Složenost i učinkovitost algoritama nova je tema koja izlazi iz okvira ovog rada. Više o njoj može se naći u [13].

 

Napomena. Članak je nastao pri izradi završnog preddiplomskog rada Ane Mimice na studiju Matematike PMF-a u Splitu. Mrežne stranice korištene su kao izvornik za slike.

Bibliografija
[1] D. Ahr, Contributions to Multiple Postmen Problems, Ph.D. thesis, University of Heidelberg, 2004
[2] E. Beltrami, Models for Public Systems Analysis, Academic Press, New York, 1977
[3] L. Bodin, A. Tucker, Model for municipal street sweeping operations, Modules in Applied Mathematics Vol. 3: Discrete and System Models, (1983), 76-111
[4] J. Edmonds, E. L. Johnson, Matching, Euler tours and the Chinese postman, Mathematical Programming, 5 (1973), 88-124
[5] L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8 (1736), 128–140
[6] J. L. Gross, J. Yellen, Graph Theory and Its Applications, CRC Press, 1999
[7] M. Guan, Graphic Programming using odd and even points, Chinese Mathematics 1, 1962
[8] D. K\H{o}nig, Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgesellschaft, Leipzig, 1936. 
Translated from German by Richard McCoart, Theory of finite and infinite graphs, Birkhäuser, 1990.
[9] T. Kramberger, J. Žerovnik, Priority Constrained Chinese Postman Problem, Logistics & Sustainable Transport, Volume 1, Issue 1, 2007
[10] B. Raghavachari, J. Veerasamy, Approximation Algorithms for Mixed Postman Problems, Lecture Notes in Computer Science, Volume 1412 (1998), 169–179
[11] T. K. Ralphs, On the Mixed Chinese Postman Problem, School of Operations Research and Industrial Engineering, Cornell University, 1993
[12] H. Robinson, Graph Theory Techniques in Model-Based Testing. Proc. of Int. Conf. and Exposition on Testing Computer Software (TCS '99), Washington (US), 1999
[13] M. Sipser, Introduction to the Theory of Computation, 2nd Edition, Course Technology, 2006
[14] Theory of Graphs and Its Applications, Proc. of the Simp. in Smolenice, Prague, 1964
[15] H. Thimbleby, The directed Chinese Postman Problem, Software Practice & Exp., 33(11)(2003), 1081-1096
[16] D. Veljan, Kombinatorna i diskretna matematika, Algoritam, Zagreb, 2001.


Prebrojavanje savršenih sparivanja

 
Frane Kalebić Joško Mandić Damir Vukičević Snježana Braić


1Uvod

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:

Definicija 1. Graf je uređena trojka G=(V,E,\varphi), gdje je V neprazan skup vrhova, E skup bridova koji je disjunktan s V, a \varphi funkcija koja svakom bridu iz E pridružuje dva, ne nužno različita vrha iz V. Graf često zapisujemo kao par G=\left( V,E\right) ili samo G.


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.


Definicija 2. Šetnja W u grafu G konačan je niz v_{0}e_{1}v_{1} e_{2}v_{2}...v_{m-1}e_{m}v_{m} čiji su članovi naizmjence vrhovi i bridovi grafa G sa svojstvom da su krajevi brida e_{i} vrhovi v_{i-1} i v_{i}, za svaki i=1,...,m. Za vrh v_{0} kažemo da je početak, a za vrh v_{m} kraj šetnje W.


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

Definicija 3. Šetnja u kojoj su svi bridovi različiti naziva se staza. Ako su pritom i svi vrhovi, osim eventualno početnog i krajnjeg, različiti, takvu stazu nazivamo put. Za šetnju kažemo da je zatvorena ako je v_{0}=v_{m}, a zatvoreni put nazivamo ciklusom.


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

Primjer 4. U nekom društvu, koje se sastoji od četiri djevojke D_{1},D_{2},D_{3},D_{4} i četiri momka M_{1},M_{2},M_{3},M_{4}, postoje neke uzajamne simpatije. Naime, djevojka D_{1} simpatizira momke M_{2} i M_{3}, djevojka D_{2} momke M_{2} i M_{4}, djevojka D_{3} momke M_{1} i M_{4}, te djevojka D_{4} simpatizira momka M_{1}. Odredite koliko najviše parova možemo povezati poštujući navedene simpatije?

Primjer 5. Neko poduzeće dalo je oglas za zapošljavanje novih djelatnika na poslove P_{1},P_{2},P_{3},P_{4} i P_{5}. Na oglas se prijavilo pet kandidata K_{1},K_{2},K_{3},K_{4} i K_{5}, s tim da je kandidat K_{1} kvalificiran za poslove P_{3} i P_{4}, kandidat K_{2} za posao P_{3}, kandidat K_{3} za poslove P_{1},P_{2} i P_{3}, kandidat K_{4} za poslove P_{3} i P_{4} te kandidat K_{5} za poslove P_{2} i P_{5}. Ispitajte je li moguće rasporediti kandidate na poslove tako da se svi poslovi obavljaju i da svaki kandidat obavlja posao za koji je kvalificiran?


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.


2Sparivanje u grafovima

Definicija 6. Sparivanje u grafu G=(V,E) je skup bridova M\subseteq E koji su karike i koji nisu međusobno susjedni. Kažemo da su vrhovi u i v spareni u M ako su u i v krajevi nekog brida iz M.


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:

Definicija 7. Sparivanje M u grafu G je maksimalno sparivanje u G ako ne postoji sparivanje u G s većim brojem bridova od broja bridova u M.

Definicija 8. Kažemo da sparivanje M u grafu G=(V,E) zasićuje vrh v\in V ili da je vrh v M-zasićen ako je v kraj nekog brida iz M. U protivnom kažemo da je vrh v M-nezasićen. Kažemo da je sparivanje M savršeno sparivanje ako je svaki vrh iz G M-zasićen.


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.
Slika 1: Primjer maksimalnog i savršenog sparivanja


Definicija 9. Za skup vrhova S\subseteq V grafa G=\left( V,E\right) kažemo da je stabilan ako nikoja dva vrha iz S nisu susjedna. Vršni pokrivač K\subseteq V je skup vrhova grafa G takvih da svaki brid od G ima barem jedan kraj u K. Bridni pokrivač L\subseteq E je skup bridova grafa G takvih da je svaki vrh grafa G kraj barem jednom bridu iz L.


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

Teorem 10. Skup S je stabilan ako i samo ako je skup V\setminus S vršni pokrivač grafa G=(V,E).


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.

Definicija 11. Neka je M sparivanje u grafu G=\left( V,E\right). M-alternirajući put u G je put čiji su bridovi naizmjenice elementi iz skupova M i E\setminus M.
M-uvećavajući put u G je M-alternirajući put čiji su početak i kraj M-nezasićeni vrhovi.

Teorem 12. [C. Berge, 1957.] Sparivanje M u grafu G je maksimalno sparivanje ako i samo ako G ne sadržava M-uvećavajući put.


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.

2.1Sparivanje u bipartitnom grafu

Definicija 13. Za graf G kažemo da je bipartitan ilidvodijelan ako se skup njegovih vrhova može podijeliti u dva disjunktna podskupa X i Y tako da svaki brid grafa G ima jedan kraj u X, a drugi u Y. Particija (X,Y) naziva se biparticija grafa G. Bipartitni graf s biparticijom (X,Y) označava se G(X,Y).


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).

Teorem 14.[Kőnig–Egerváry, 1931.] U bipartitnom grafu G broj bridova maksimalnog sparivanja jednak je broju vrhova minimalnog pokrivača, tj. vrijedi jednakost \upsilon (G)=\tau(G).

Definicija 15. Kažemo da bipartitni graf G(X,Y) ima potpuno sparivanje u X ako postoji sparivanje u Gkoje zasićuje sve vrhove iz X.


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.

Teorem 16.[P. Hall, 1935.] Bipartitni graf G s biparticijom (X,Y) ima potpuno sparivanje ako i samo ako za svaki S\subseteq X vrijedi Hallov uvjet:
\left\vert N\left( S\right) \right\vert \geq\left\vert S\right\vert ,
gdje je N(S)\subseteq Y skup svih vrhova grafa G koji su susjedni vrhovima iz S.


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.

Teorem 17.[Teorem o braku] Bipartitni graf G s particijom (X,Y) ima savršeno sparivanje ako i samo ako je \left\vert X\right\vert =\left\vert Y\right\vert i \left\vert N(S)\right\vert \geq\left\vert S\right\vert , za svaki S\subseteq X.


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.

2.2Mađarska metoda

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.
Animirani prikaz mađarske metode

 

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.

3Prebrojavanje Kekuléovih struktura

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.

3.1Linearne rekurzivne metode

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.
Slika 2: Kekuléove strukture naftalena


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
(1)
K(G)=K(G-e)+K(G\circleddash e)
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.


3.2Metode transfer matrice

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
K_{L}=tr\left( \rho\cdot T^{L}\right)
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.
Primjer 18. Nađimo transfer matricu za lanac polifena dug 14 heksagona.


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
\begin{bmatrix} g\rightarrow g & g\rightarrow d\\ d\rightarrow g & d\rightarrow d \end{bmatrix} \Rightarrow T= \begin{bmatrix} 1 & 1\\ 0 & 1 \end{bmatrix}.

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.

Primjer 19. Odredimo transfer matrice za lanac prikazan na donjoj slici.



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.
Slika 3: nije dobro


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.
Slika 4: dobro


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.
Slika 5: nije dobro


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.
Slika 6: nije dobro


Dakle, transfer matrica je oblika
\begin{bmatrix} g\rightarrow g & g\rightarrow s & g\rightarrow d & g\rightarrow gsd\\ s\rightarrow g & s\rightarrow s & s\rightarrow d & s\rightarrow gsd\\ d\rightarrow g & d\rightarrow s & d\rightarrow d & d\rightarrow gsd\\ gsd\rightarrow g & gsd\rightarrow s & gsd\rightarrow d & gsd\rightarrow gsd \end{bmatrix} \Rightarrow T= \begin{bmatrix} 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix},
što možemo poistovjetiti s matricom reda 3 oblika
T= \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix}.
Lako se provjeri da je
T^{n}= \begin{bmatrix} 1 & n & \frac{n\left( n+1\right) }{2}\\ 0 & 1 & n\\ 0 & 0 & 1 \end{bmatrix},
pa dobivamo broj Kekuléovih struktura u lancu duljine L u eksplicitnom obliku
K_{L}=3+2L+\frac{1}{2}L\left( L+1\right).

Uočimo da je ova eksplicitna jednadžba analogna linearnoj rekurziji 1. Ako označimo karakteristični polinom transfer matrice reda n s
p\left( x\right) =\det\left( xI-T\right) =-\sum_{i=0}^{n}a_{i}x^{n-i},
onda je, po Hamilton-Cayleyevu teoremu, T^{n}=\sum\limits_{i=1}^{n} a_{i}T^{n-i}, pa je
K_{L+1}=tr\left( \rho\cdot T^{L+1-n}\cdot T^{n}\right) =\sum_{i=1}^{n} a_{i}tr\left( \rho\cdot T^{L+1-i}\right) =\sum\limits_{i=1}^{n} a_{i}K_{L+1-i},

š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.
Bibliografija
[1] D. Veljan, Kombinatorna i diskretna matematika, Algoritam, Zagreb 2001.
[2] Wilson, J. Robin, Introduction to Graph Teory, Longman 1972.
[3] Mario Osvin Pavčević, Uvod u teoriju grafova, Element, Zagreb 2006.
[4] Diestel, Reinhald, Graph Theory, New York 2000.
[5] www.grinvin.org, Graph Theory Software
[6] D. J. Klein, D. Babić and N. Trinajstić, Enumeration in Chemistry, Chemical Modelling: Applications and Theory, Volume 2, The Royal Society of Chemistry, 2002.
[7] I. Gutman, O. E. Polanski, Mathematical Concepts in Organic Chemistry, Springer-Verlag, Berlin, 1986.
[8] D. Veljan, Kombinatorika s teorijom grafova, Školska knjiga, Zagreb, 1989.

Kvantitativne metode odlučivanja – problem optimalne zamjene opreme

mr. sc. Bojan Kovačić, dipl. ing. matematike,
RRiF – Visoka škola za financijski menadžment,
10 000 Zagreb,
Martićeva 29,
e-mail: bojan.kovacic@rrif.hr




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.

Primjer 1


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:



starost automobila (i) [god.] 0 1 2 3 4 5
godišnji neto trošak održavanja (c_{i}) [n.j.] 2 4 5 9 12 12
likvidacijska vrijednost (s_{i}) [n.j.] - 7 6 2 1 0

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
\binom{n+1}{2}=\binom{6}{2} = 15 \text{.}
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:
\begin{split} w_{ij}&= (\text{nabavna cijena automobila na početku godine } i)\\ &\quad + (\text{troškovi održavanja u godinama } i, i + 1, \ldots, j - 1) \\ &\quad - (\text{likvidacijska vrijednost automobila na početku godine } j). \end{split}
Odatle slijedi da je analitički izraz za izračunavanje težina w_{ij}:
w_{ij} = p_{i} + c_{0} + c_{1} + \ldots + c_{j-1-i}-s_{j-i} = p_{i} + \sum_{k=0}^{j-i-1}c_{k} - s_{j-i}.
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:
w_{ij} = w_{i+k,j+k} ,
za sve i,j,k za koje su definirane obje strane jednakosti. Tako se dobiva:
\begin{align*} w_{12}& = w_{23} = w_{34} = w_{45} = w_{56} = p + c_{0} - s_{1} = 12+2-7 = 7 ; \\ w_{13}& = w_{24} = w_{35} = w_{46} = p + (c_{0} + c_{1}) - s_{2} = 12+2+4-6 = 12 ; \\ w_{14}& = w_{25} = w_{36} = p + (c_{0} + c_{1} + c_{2}) - s_{3} = 12+2+4+5-2 = 21 ; \\ w_{15}& = w_{26} = p + (c_{0} + c_{1} + c_{2} + c_{3}) - s_{4} = 12+2+4+5+9-1 = 31 ; \\ w_{16}& = p + (c_{0} + c_{1} + c_{2} + c_{3} + c_{4}) - s_{5} = 12+2+4+5+9+12-0 = 44 \text{.} \end{align*}

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.
Slika 1: Model problema iz primjera 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:

1246.

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:

1356.

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.

Primjer 2


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:



starost bicikla (i) [god.] 0 1 2 3
godišnji neto trošak (c_{i}) [n.j.] 30 40 60 -
likvidacijska vrijednost (s_{i}) [n.j.] - 400 300 250

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
\frac{p + (c_{0} + c_{1}) - s_{2}}{2} = \frac{500 + (30 + 40) - 300}{2} = 135 \text{ n.j.}

Ako Ivan kupi bicikl, bude li ga koristio sve tri godine i potom ga prodao, prosječan godišnji neto trošak iznosit će
\frac{p + (c_{0} + c_{1} + c_{2}) - s_{3}}{3} = \frac{500 + (30 + 40 + 60) - 250}{3} = 126.67 \text{ n.j.}

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:
\begin{align*} w_{12}& = w_{23} = w_{34} = w_{45} = w_{56} = p + c_{0} - s_{1} = 500+30-400 = 130 ; \\ w_{13}& = w_{24} = w_{35} = w_{46} = p + (c_{0} + c_{1}) - s_{2} = 500+(30+40)-300 = 270 ; \\ w_{14}& = w_{25} = w_{36} = p + (c_{0} + c_{1} + c_{2}) - s_{3} = 500+(30+40+60)-250 = 380 \text{.} \end{align*}

Težinski digraf dobiven uz pomoć programa Graph Magics prikazan je na slici 2.
Slika 2: Model problema iz primjera 2.

Najkraći put između vrhova 1 i 6 je

1236,

č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.

Primjer 3


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:



starost automobila (i) [god.] 0 1 2 3 4
godišnji neto trošak (c_{i}) [n.j.] 10 20 40 60 70

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:
s_{i} = s(i) = 25 - 5 \cdot i \text{, za } i=1,2,3,4,5 \text{.}
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:
\begin{align*} V(k,i) = \ & \text{najmanji ukupni neto troškovi od početka godine }k\text{ do kraja} \\ & \text{razdoblja planiranja (tj. početka godine }n + 1\text{) ako na početku} \\ & \text{godine }k\text{ raspolažemo vozilom starosti }i\text{.} \end{align*}

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:
V(k, i) = \min \Big\lbrace c_{i} + V(k + 1, i + 1), \ p + c_{0} - s_{i} + V(k + 1, 1)\Big\rbrace \text{.}
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:
\begin{align*} V(4, 1) &= -s_{1} = -(25 - 5 \cdot 1) = -20 ; \\ V(4, 2) &= -s_{2} = -(25 - 5 \cdot 2) = -15 ; \\ V(4, 3) &= -s_{3} = -(25 - 5 \cdot 3) = -10 ; \\ V(4, 4) &= -s_{4} = -(25 - 5 \cdot 4) = -5 ; \\ V(4, 5) &= -s_{5} = -(25 - 5 \cdot 5) = 0 \text{.} \end{align*}

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:
\begin{align*} V(3, 1) &= \min \big\lbrace c_{1} + V(3 + 1, 1 + 1), \ p + c_{0} - s_{1} + V(3 + 1, 1)\big\rbrace \\ &= \min \big\lbrace 20 + V(4, 2), \ 60 + 10 - 20 + V(4, 1)\big\rbrace \\ &= \min \big\lbrace 20 + (-15), \ 50 + (-20)\big\rbrace = 5 ; \\ V(3, 2) &= \min \big\lbrace c_{2} + V(3 + 1, 2 + 1), \ p + c_{0} - s_{2} + V(3 + 1, 1)\big\rbrace \\ &= \min \big\lbrace 40 + V(4, 3), \ 60 + 10 - 15 + V(4, 1)\big\rbrace \\ &= \min \big\lbrace 40 + (-10), \ 55 + (-20)\big\rbrace = 30 ; \\ V(3, 3) &= \min \big\lbrace c_{3} + V(3 + 1, 3 + 1), \ p + c_{0} - s_{3} + V(3 + 1, 1)\big\rbrace \\ &= \min \big\lbrace 60 + V(4, 4), \ 60 + 10 - 10 + V(4, 1)\big\rbrace \\ &= \min \big\lbrace 60 + (-5), \ 60 + (-20)\big\rbrace = 40 ; \\ V(3, 4) &= \min \big\lbrace c_{4} + V(3 + 1, 4 + 1), \ p + c_{0} - s_{4} + V(3 + 1, 1)\big\rbrace \\ &= \min \big\lbrace 70 + V(4, 5), \ 60 + 10 - 5 + V(4, 1)\big\rbrace \\ &= \min \big\lbrace 70 + 0, \ 65 + (-20)\big\rbrace = 45 \text{.} \end{align*}

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:
\begin{align*} V(2, 1) &= \min \big\lbrace c_{1} + V(2 + 1, 1 + 1), \ p + c_{0} - s_{1} + V(2 + 1, 1)\big\rbrace \\ &= \min \big\lbrace 20 + V(3, 2), \ 60 + 10 - 20 + V(3, 1)\big\rbrace \\ &= \min \big\lbrace 20 + 30, \ 50 + 5\big\rbrace = 50 ; \\ V(2, 2) &= \min \big\lbrace c_{2} + V(2 + 1, 2 + 1), \ p + c_{0} - s_{2} + V(2 + 1, 1)\big\rbrace \\ &= \min \big\lbrace 40 + V(3, 3), \ 60 + 10 - 15 + V(3, 1)\big\rbrace \\ &= \min \big\lbrace 40 + 40, \ 55 + 5\big\rbrace = 60 ; \\ V(2, 3) &= \min \big\lbrace c_{3} + V(2 + 1, 3 + 1), \ p + c_{0} - s_{3} + V(2 + 1, 1)\big\rbrace \\ &= \min \big\lbrace 60 + V(3, 4), \ 60 + 10 - 10 + V(3, 1)\big\rbrace \\ &= \min \big\lbrace 60 + 45, \ 60 + 5\big\rbrace = 65 \text{.} \end{align*}

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:
\begin{align*} V(1, 1) &= \min \big\lbrace c_{1} + V(1 + 1, 1 + 1), \ p + c_{0} - s_{1} + V(1 + 1, 1)\big\rbrace \\ &= \min \big\lbrace 20 + V(2, 2), \ 60 + 10 - 20 + V(2, 1)\big\rbrace \\ &= \min \big\lbrace 20 + 60, \ 50 + 50\big\rbrace = 80 ; \\ V(1, 2) &= \min \big\lbrace c_{2} + V(1 + 1, 2 + 1), \ p + c_{0} - s_{2} + V(1 + 1, 1)\big\rbrace \\ &= \min \big\lbrace 40 + V(2, 3), \ 60 + 10 - 15 + V(2, 1)\big\rbrace \\ &= \min \big\lbrace 40 + 65, \ 55 + 50\big\rbrace = 105 \text{.} \end{align*}

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.

Primjer 4


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):
d_{i} = d(i) = \begin{cases} 120-20 \cdot i, & \text{za }i=0\text{, }1\text{, }2\text{, }3\text{, }4\text{, }5\text{}; \\ 0, & \text{za }i \geq 6\text{.} \end{cases}
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:
\begin{align*} V=V(k,i) = \ & \text{najveća ukupna neto dobit ostvarena od početka godine }k\text{ do} \\ & \text{kraja razdoblja planiranja ako se na početku godine }k\text{ raspolaže} \\ & \text{opremom starom }i\text{ godina.} \end{align*}
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:
\begin{align*}V(k,i) &= \max \big\lbrace d_{i} + V(k + 1, i + 1), \ d_{0} - p + V(k + 1, 1) \big\rbrace \\ &= \max \big\lbrace d_{i} + V(k + 1, i + 1), \ 120 - 120 + V(k + 1, 1) \big\rbrace \\ &= \max \big\lbrace d_{i} + V(k + 1, i + 1), \ V(k + 1, 1) \big\rbrace \text{.}\end{align*}

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:
V(k,i)=0 ,
izraz za izračunavanje vrijednosti V(8, i) može se transformirati ovako:
\begin{align*}V(8, i) &= \max \big\lbrace d_{i} + V(8 + 1, i + 1), \ d_{0} - p + V(8 + 1, 1) \big\rbrace \\ &= \max \big\lbrace d_{i} + V(9, i + 1), \ 120 - 120 + V(9, 1) \big\rbrace \\ &= \max \big\lbrace d_{i} + 0, \ 0 \big\rbrace = d_{i} \text{.}\end{align*}
Dobiva se:



i 0 1 2 3 4 5 6 7 8 9 10
V(8,i) 120 100 80 60 40 20 0 0 0 0 0

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:
\begin{align*} V(7, 0) &= \max \big\lbrace d_{0} + V(7 + 1, 0 + 1), \ V(7 + 1, 1) \big\rbrace \\ &= \max \big\lbrace 120 + V(8, 1), \ V(8, 1) \big\rbrace = \max \big\lbrace 120 + 100, \ 100 \big\rbrace = 220 ; \\ V(7, 1) &= \max \big\lbrace d_{1} + V(7 + 1, 1 + 1), \ V(7 + 1, 1) \big\rbrace \\ &= \max \big\lbrace 100 + V(8, 2), \ V(8, 1) \big\rbrace = \max \big\lbrace 100 + 80, \ 100 \big\rbrace = 180 ; \\ V(7, 2) &= \max \big\lbrace d_{2} + V(7 + 1, 2 + 1), \ V(7 + 1, 1) \big\rbrace \\ &= \max \big\lbrace 80 + V(8, 3), \ V(8, 1) \big\rbrace = \max \big\lbrace 80 + 60, \ 100 \big\rbrace = 140 ; \\ V(7, 3) &= \max \big\lbrace d_{3} + V(7 + 1, 3 + 1), \ V(7 + 1, 1) \big\rbrace \\ &= \max \big\lbrace 60 + V(8, 4), \ V(8, 1) \big\rbrace = \max \big\lbrace 60 + 40, \ 100 \big\rbrace = 100 ; \\ V(7, 4) &= V(7, 5) = V(7, 6) = V(7, 7) = V(7, 8) = V(7, 9) = V(8, 1) = 100 \end{align*}
(š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:
\begin{align*} V(6,0) & = 300, \ V(6,1) = 240, \ V(6,2) = 180, \\ V(6,3) & = V(6,4) = V(6,5) = V(6,6) = V(6,7) = V(6,8) = 180 \end{align*}
(što znači da ako se početkom šeste godine raspolaže opremom starom barem dvije godine, svakako se isplati kupiti novu);
\begin{align*} V(5,0) & = 360, \ V(5,1) = 280, \ V(5,2) = 260, \ V(5,3) = 240, \\ V(5,4) & = V(5,5) = V(5,6) = V(5,7) = 240 \end{align*}
(što znači da ako se početkom pete godine raspolaže opremom starom barem tri godine, svakako se isplati kupiti novu);
\begin{align*} V(4,0) & = 400, \ V(4,1) = 360, \ V(4,2) = 320, \ V(4,3) = 300, \ V(4,4) = 280, \\ V(4,5) &= V(4,6) = 280 \end{align*}
(što znači da ako se početkom četvrte godine raspolaže opremom starom barem četiri godine, svakako se isplati kupiti novu);
\begin{align*} V(3,0) & = 480, \ V(3,1) = 420, \ V(3,2) = 380, \ V(3,3) = 360, \\ V(3,4) &= V(3,5) = 360 \end{align*}
(što znači da ako se početkom treće godine raspolaže opremom starom barem tri godine, svakako se isplati kupiti novu);
V(2,0) = 540, \ V(2,1) = 480, \ V(2,2) = 440, \ V(2,3) = 420, \ V(2,4) = 420
(što znači da ako se početkom druge godine raspolaže opremom starom barem tri godine, svakako se isplati kupiti novu);
V(1,0) = 600, \ V(1,1) = 540, \ V(1,2) = 500, \ V(1,3) = 480\text{.}
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.

Primjer 5


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:
\begin{split} w_{ij} & = \text{(ukupna neto dobit nastala korištenjem opreme u godinama} \\ & \qquad \text{}i\text{, }i + 1\text{, }\ldots\text{, }j - 2\text{, }j - 1\text{)} - \text{(nabavna cijena opreme u godini }i\text{)} \\ & = \sum_{k=0}^{j-i-1}d_{k} - p_{i} . \end{split}

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:
\begin{gather*} w_{i,i+1} = 0 , \\ w_{i,i+k} = \sum_{m=1}^{k-1}d_{k} , \ \text{ za svaki }k \in \mathbb{N} \setminus \lbrace 1\rbrace \text{ za koji postoji luk }(i,i+k)\text{.} \end{gather*}
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
\begin{align*} d_{1} & = 120 - 20 \cdot 1 = 100 ; & d_{5} & = 120 - 20 \cdot 5 = 20 ; \\ d_{2} & = 120 - 20 \cdot 2 = 80 ; & d_{6} & = 120 - 20 \cdot 6 = 0 ; \\ d_{3} & = 120 - 20 \cdot 3 = 60 ; & d_{7} & = 0 ; \\ d_{4} & = 120 - 20 \cdot 4 = 40 ; & d_{8} & = 0 , \end{align*}
slijedi:
\begin{align*} w_{12} & = w_{23} = w_{34} = w_{45} = w_{56} = w_{67} = w_{78} = w_{89} = 0 ; \\ w_{13} & = w_{24} = w_{35} = w_{46} = w_{57} = w_{68} = w_{79} = d_{1} = 100 ; \\ w_{14} & = w_{25} = w_{36} = w_{47} = w_{58} = w_{69} = d_{1} + d_{2} = 100 + 80 = 180 ; \\ w_{15} & = w_{26} = w_{37} = w_{48} = w_{59} = d_{1} + d_{2} + d_{3} = 100 + 80 + 60 = 240 ; \\ w_{16} & = w_{27} = w_{38} = w_{49} = d_{1} + d_{2} + d_{3} + d_{4} = 100 + 80 + 60 + 40 = 280 ; \\ w_{17} & = w_{28} = w_{39} = d_{1} + d_{2} + d_{3} + d_{4} + d_{5} = 100 + 80 + 60 + 40 + 20 = 300 ; \\ w_{18} & = w_{29} = d_{1} + d_{2} + d_{3} + d_{4} + d_{5} + d_{6} = 100 + 80 + 60 + 40 + 20 + 0 = 300 ; \\ w_{19} & = d_{1} + d_{2} + d_{3} + d_{4} + d_{5} + d_{6} +d_{7} = 100 + 80 + 60 + 40 + 20 + 0 + 0 = \\ & = 300 \text{.} \end{align*}

Uz pomoć računalnoga programa Grin dobiva se digraf prikazan na slici 3.
Slika 3: Model problema iz primjera 5.

Primjenom procedure Critical Path implementirane u istom računalnom programu određuje se kritični put u tom digrafu:

159.

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]).

Bibliografija
[1] Schun–Chen Niu, Dynamic Programming, School of Management, University of Texas, Dallas, http://www.utdallas.edu/ scniu/OPRE-6201/documents/DP2-Equipment-Replacement.pdf, 15. 6. 2009.
[2] Farid AitSahlia, Operations Research 2, Industrial and Systems Engineering, University of Florida, Weil Hall, http://www.ise.ufl.edu/esi4313/DP.ppt, 15. 6. 2009.
[3] Michael Trick, Dynamic Programming, Tepper School of Business, Carnegie Mellon University, Pittsburg, http://mat.gsia.cmu.edu/classes/dynamic/node7.html, 15. 6. 2009.
[4] Maja Fošner, Tomaž Kramberger, Teorija grafova i logistika, math.e, broj 14, http://e.math.hr/math_e_article/br14/fosner_kramberger, Zagreb, 2009.
[5] Richard E. Bellman, Dynamic Programming, Courier Dover Publication, 2003.
[6] Blaženka Divjak, Alen Lovrenčić, Diskretna matematika s teorijom grafova, FOI – TIVA, Varaždin, 2005.
[7] Jovan Petrić, Operaciona istraživanja, Nauka, Beograd, 1997.
[8] Jovan Petrić, Lazar Šarenac, Zdravko Kojić, Operaciona istraživanja – zbirka rešenih zadataka, Nauka, Beograd, 1996.


Teorija grafova i logistika

 


Maja Fošner i Tomaž Kramberger
University of Maribor
Faculty of Logistics
Mariborska cesta 2
3000 Celje
Slovenia
maja.fosner@uni-mb.si
tomaz.kramberger@uni-mb.si



Sažetak
U ovom radu bavimo se logistikom i teorijom grafova. Opisujemo vezu logističkih problema iz svakidašnjeg života i teorije grafova.

1Uvod

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.

2Neke definicije

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.


Slika 1: Usmjeren graf sa šest vrhova i sedam bridova.


Slika 2: Neusmjeren i usmjeren graf.


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).


Slika 3: Višestruki brid između vrhova u i v.


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.


Slika 4: 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).


Slika 5: Graf i podgraf.



3Šetnja i duljina u grafu

Š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.


Slika 6: Šetnja utzw je put između u i w.


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).


Slika 7: Udaljenost između vrhova u i v je duljina najkraćeg puta među njima.


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.


Slika 8: Povezani i nepovezani graf.


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).


Slika 9: Graf i razapinjuće stablo.



4Problem Sedam königsberških mostova

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.


Slika 10: Četiri dijela grada i sedam mostova u Königsbergu.


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.


Slika 11: Model Köningsberga i mostova predočen u teoriji grafova.


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.
Bibliografija
[1] Eiselt, H. A., Gendreau, M., Laporte, G., Arc routing problem I: The Chisenese postman problem, Operations Research 43(2), (1995) 231-242.
[2] Kramberger, T., Žerovnik, J., Priority constrained Chinese postman problem: Logistics and Sustainable Transport, 1(1), (2007) 15 str.
[3] Wilson, J. R., Watkins, J. J., Uvod v teorijo grafov, DMFA, Slovenija, (1997).
[4] Guan, M., Graphic Programming using odd and even points, Chinese Mathematics 1, (1962) 273-277.
[5] Korte, B., Vygen J., Combinatorial optimization: Theory and algorithms, Springer, Berlin, Heidelberg, New York, (2002).