logicki problemi

Pokusavam da resim problem Kenizberških mostova, ali nikako ne ide. Je li neko od vas uspeo da resi i kako?

0 za

0 protiv

onshort
2012-01-28

Kalinjingrad (nem. Königsberg) je glavni grad istoimene oblasti, ruske enklave između Poljske i Litvanije, sa pristupom Baltičkom moru.

Zadatak na koji se pitanje odnosi postavio je Leonard Ojler u XVIII veku. On je pokazao da se zadatak o keningsberškim mostovima svodi na zadatak crtanja mreže u ravni u jednom potezu (ne podižući olovku sa hartije), ne prelazeći po već povučenoj liniji.

Takva jedna zatvorena mreža, koja se sastoji od tačaka (čvorova) i linija koje spajaju ove tačke, a ne presecaju se međusobno, mogu se predstaviti pomoću grafa. Dva čvora grafa zovu se susedna ako su spojena linijom. Za grafove koji se mogu nacrtati na pomenuti način kaže se da poseduju Ojlerov put.

Teorema koja daje uslove za postizanje Ojlerovog puta glasi: Graf poseduje Ojlerov put ako i samo ako ima dva ili nijedan čvor neparnog reda.

Tako, na osnovu Ojlerove teoreme, prelaz preko sedam keningsberških mostova nije moguće izvršiti u jednom potezu.

Nadam se da ti je bar zadnja rečenica jasna.