Zobrazenie zdroja stránky Problém siedmich mostov

[[Súbor:Konigsberg bridges.png|thumb|Mapka Kaliningradu z [[Leonhard Euler|eulerovských]] dôb s vyznačenými siedmimi mostami]]
'''Problém siedmich mostov''' mesta [[Kaliningrad]] (po rusky Калининград, do 4. júla 1946 po nemecky Königsberg, po poľsky Królewiec, po slovensky Kráľovec) je slávny, ale už vyriešený matematický problém založený na skutočnom mieste a skutočnej udalosti.

Mesto Kaliningrad sa rozprestiera na brehoch a ostrovoch rieky [[Pregola|Pregoly]]. Medzi jednotlivými brehmi a ostrovmi vedie sedem mostov. Obyvateľov mesta zaujímalo, či môžu pri svojich promenádach prejsť všetky mosty takým spôsobom, že sa dostanú opäť do pôvodného miesta, bez toho aby nejaký most prešli viackrát.<ref name="kolar">KOLÁŘ J., 2004, Teoretická informatika, Praha, Česká informatická společnost, 2. vydanie, ISBN 80-900853-8-5</ref>

[[Súbor:Königsberg graph.svg|náhľad|Sedem mostov mesta [[Kaliningrad]] zobrazených ako graf]]

[[Leonhard Euler]] nahradil všetky časti súše vrcholmi a všetky mosty hranami spájajúcimi tieto vrcholy. Týmto spôsobom previedol tento problém na úlohu nájsť taký ťah v grafe, ktorý by obsahoval každú hranu práve raz. Takýto ťah nazývame [[Eulerovský ťah]].<ref name="knor">KNOR M., 2000, KOMBINATORIKA A TEÓRIA GRAFOV I, Univerzita Komenského Bratislava, Vydavateľstvo UK, 1. vydanie, ISBN 80-223-1339-4</ref>

== Riešenie ==
'''Veta:''' [[Neorientovaný graf]] <math>G</math> má uzavretý Eulerovský ťah práve vtedy ak je súvislý a ak <math>\forall v \in V(G)</math> platí <math>d(v)\mod 2 = 0</math>

'''Veta:''' Ak <math>G</math> je súvislý, neorientovaný graf ktorý obsahuje práve 2 vrcholy pre ktoré platí <math>d(v) \mod 2 = 1</math> hovoríme, že graf má otvorený Eulerovský ťah.

Tieto 2 vety nám hovoria o tom, že ak obrázok chcem nakresliť jedným ťahom potom do všetkých vrcholov musí smerovať párny počet hrán resp. práve do dvoch nepárny počet.

Z obrázkov teda už vidíme, že obyvatelia mesta Kaliningrad nemohli prejsť všetky mosty práve 1-krát a to ani v tom prípade ak by sme zrušili podmienku, že sa musia vrátit na rovnaké miesto.

== Referencie ==

<references />

[[Kategória:Teória grafov]]