Predmet:
Modeli optimizacije u transportu
PROBLEM KINESKOG POŠTARA
SEMINARSKI RAD
MENTOR
:
STUDENT
:
Podgorica, 16.02.2019. godine
1
SADRŽAJ
1.Uvod
………………………………………………………………….2
2.Problem kineskog poštara
………………………………………….3
3. Problem kineskog poštara na neorjentisanim mrežama
…………5
4. Problem kineskog poštara na orjentisanim mrežama
…………..9
5. Primjer
………………………………………………………………10
5.1. Primjer 1 …………………………………………………………10
5.2. Primjer 2 …………………………………………………………13
6.Zaključak
…………………………………………………………….14
7.Literatura
……………………………………………………………..15
3
2. Problem kineskog poštara
Jedan poštar je odgovoran za raznošenje pošte u dijelu grada. On započinje sa raznošenjem
pošte iz odeđenog čvora u kome je locirana pošta i tokom radnog vremena mora da obiđe sve
ulice u posmatranom dijelu grada najmanje jednom, da bi se na završetku radnog vremena
vratio u poštu. Postavlja se pitanje: koja je to ruta kojom treba da se kreće poštar, tako da
rastojanje koje pređe bude minimalno, pri čemu svaku ulicu treba da obiđe najmanje jedanput.
Koristeći se terminologijom transportnih mreža ovo pitanje glasi: koji je najkraći put kojim
treba da se krećemo kroz transportnu mrežu, tako da kroz sve grane mreže prođemo barem
jednom i da se na kraju vratimo u čvor iz koga smo krenuli.
Jedan od najpoznatijih problema je upravo Problem sedam mostova Koeningsberga za koji je
1735. godine švajcarski naučnik Leonhard Euler donio negativan zaključak. Naime,
Koeningsberg je bio glavni grad Prusije od kasnih godina srednjeg doba pa sve do 1701.
godine kada je glavni grad postao Berlin. Izgrađen je s obje strane rijeke Pregel i na dva riječna
ostrva, mostovi povezuju obje strane rijeke i ostrva.
Građani Koenigsberga zabavljali su se starim pitanjem mogu li prošetati svojim gradom tako
da svaki od 7 mostova na rijeci Pregel pređu tačno jedanput i završe šetnju u polaznoj tački.
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.
Slika 1: Problem 7 mostova
4
Rješavanje problema kineskog poštara povezano je sa definicijama Euler – ovog puta. Bitno je
naglasiti razliku između pojmova Euler – ovog puta i Euler – ove ture.
Pod Euler – ovom turom se podrazumijeva ciklus kojim se kroz svaku granu granu u mreži
prolazi tačno jedanput i vraća se u početni položaj. Euler – ov put je put kojim se kroz svaku
granu u mreži prolazi tačno jedanput pri čemu se put ne završava u čvoru iz koga je počeo.
Kao primjer Euler – ove ture u ovom slučaju može
nam poslužiti ciklus {b, e, b, c, e, f, c, d, f, d, a,
b }. Na osnovu ovog ciklusa možemo vidjeti da se
kroz svaku tačku prolazi barem jednom i da je
početna tačka (b) ujedno i krajnja tačka ove ture.
Slika 2 : Mreža koja posjeduje Euler - ovu turu
U prikazanoj mreži možemo dati primjer Euler –
ovog puta {b, a, e, c, a, d, c f, d, i, f, e, b, h, e, g, h,
j, g, f, j, i} gdje možemo uočiti da se po prolasku
kroz sve grane mreže ne vraćamo u čvor iz koga
smo krenuli jer je b≠i.
Slika 3: Mreža koja posjeduje Euler - ov put
