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. Šematski prikaz, na kojem su dijelovi kopna (obale B i C i
ostrva A i D) predstavljeni tačkama a mostovi njihovim spojnicama, prototip je modela koji će
odrediti definiciju pojma grafa.

Početkom 60-tih godina dvadesetog vijeka, kineski matematičar

M. Guan (Meigu Guan ili Mei-

Ko Kwan)

postavlja i proučava pitanje optimizacije poštarovog puta pri dostavi pošiljki. Poštar

kreće iz pošte, dijeli poštu i vraća se u ured. Poštarov cilj je svakom ulicom proći barem
jedanput i pri tome preći najkraći mogući put. U slučaju koenigsberških mostova, analogan
zadatak bi bio: prošetati gradom i vratiti se u polaznu tačku, prelazeći svaki most najmanje
jedanput uz minimalan broj ponovljenih prelazaka. Guanovo pitanje će doživljeti brojne
modifikacije i imati raznovrsne primjene. Taj tip problema njemu u čast nazvan je Problem
kineskog poštara. Optimizacijske probleme i kombinatorne probleme uopšteno, relativno je
lako formulisati, ali njihovo rešavanje je rijetko kada jednostavno. Za sistemsko traženje rešenja
potrebno je pronaći primjerene matematičke modele i metode.

PROBLEM KINESKOG POŠTARA

Jedan od najpoznatijih i najviše izučavanih problema kombinatorne optimizacije je već
pomenuti Problem kineskog poštara, skraćeno CCP (

eng. Chinese Postman Problem

). Naznačeni

problem se sastoji u sledećem:

Jedan poštar je odgovoran za raznošenje pošte u dijelu grada. On započinje sa raznošenjem
pošte iz određenog čvora u kome je locirana pošta i tokom radnog vremena mora da obiđe sve
ulice u posmatranom dijelu grada najmanje jedanput, da bi se na završetku radnog vremena
vratio u poštu. Logično je da sebi postavimo sledeće 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.

Prevedeno na terminologiju 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 najmanje

PROBLEM KINESKOG POŠTARA

jedanput i da se na kraju vratimo u čvor iz koga smo krenuli. Ovaj problem prvi put je izučavan
od strane

Mei-Ko

-a

(1962)

. Rad

Mei-Ko

-a je objavljen u časopisu

“Chinese Mathematics“

, zbog

čega je naznačeni problem nazvan problemom kineskog poštara. Rešavanje problema kineskog
poštara povezano je sa definicijama

Euler

-ovog puta.

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

Euler

-ovom turom se podrazumijeva ciklus kojim se kroz svaku granu u mreži prolazi tačno

jedanput. Proučavajući problem

“sedam mostova u Kenigzbergu“ Leonard Euler (1707-1783)

u svom radu objavljenom 1736. godine od strane akademije nauka u Sankt Peterzburgu utvrdio
u kojim slučajevima mreža posjeduje

Euler

-ovu turu i

Euler-

ov put.

Problem kineskog poštara može se javiti na:

1. neorijentisanim;
2. orijentisanim i
3. mješovitim mrežama.

U zavisnosti od saobraćajno-transportnog problema koji se razmatra, pod poštarom mogu da
se podrazumijevaju vozila za pranje ulica, vozila za čišćenje ulica od snijega, vozila za skupljanje
smeća u gusto naseljenim ulicama, vozila koja se koriste za popravku i inspekciju komunalne
infrastrukture (električna, vodovodna i kanalizaciona instalacija).

PROBLEM KINESKOG POŠTARA NA NEORIJENTISANIM MREŽAMA

Neka je data neorijentisana mreža G = (N, A) i neka su poznate dužine svih grana d(i, j)>0,
(i, j)

∈

A. Kao i obično, veličine d(i, j) mogu takođe da predstavljaju i troškove, vrijeme putovanja

ili bilo šta drugo u zavisnosti od naznačenog problema. Problem kineskog poštara možemo
formulisati na sledeći način:

Pronađimo ciklus kojim je moguće proći kroz sve grane mreže G najmanje jedanput i za koji:

U cilju rešavanje ovog problema neophodno je prethodno definisati

Euler

-ovu turu i

Euler

-ov

put.