Keningzberški mostovi

Objavljeno: 04 Oktobar 2008Klikova: 5652

 

Godine 1736. građani Keningzberga, grada koji je smješten na obalama i ostrvima rijeke Pregel, postavili su pitanje da li je moguće, šetajućii gradom, preći preko svih sedam mostova tako da se nijedan od njih ne pređe više od jednom.

 

 

 

 

 

 

 

 

 

 

 

 

Za ovaj problem se pored ostalih zainteresovao i Ojler. Označio je mostove linijama, a ostrva i obale kružićima
(čvorovima) i sliku na lijevoj strani je zamijenio prikazanim grafom.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Na ovaj način problem Keningzberških mostova je sveo na sljedeći zadatak:

 

Može li se graf sa slike nacrtati "jednim potezom", tj. tako da se olovka ne podiže s papira i ne prelazi dva puta po jednoj liniji.

 

Odgovor na postavljeno pitanje je negativan. Povezan graf uz zadane uslove može se nacrtati "jednim potezom" samo ako ima dva ili nijedan čvor u kojem se sastaje neparan broj linija. Kako se u ovom grafu u sva četiri čvora sastaje neparan broj linija to se on ne može nacrtati "jednim potezom". Dakle, ne može šetajući se po Kenigzbergu preći preko svih sedam mostova tako da se nijedan od njih ne pređe više od jedanput.

Share this post
FaceBook  Twitter