Problem kineskog poštara

Određivanje optimalne rute vozila je sam za sebe poznati kombinatorni problem. Čovjek se svakodnevno suočava s problemima traženja puta od početne tačke A do odredišta B. Svaki takav problem svodi se na rješavanje problema korišćenjem mrežnog modela.

Jedan od najpoznatijih i najviše izučavanih problema u problematici pokrivanja grana je problem kineskog poštara. Ovaj problem prvi put je izučavan od strane Mei – Ko – a i to 1962. godine. 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štanske kancelarije, dijeli poštu i vraća se nazad. Poštarov cilj je svakom ulicom proći barem jednom i pri tome preći najkraći mogući put. Rad Mei – Ko – a je objavljen u časopisu „Chinese Mathematics‟, zbog čega je i ovaj problem nazvan problemom kineskog poštara.