A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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 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.[1]
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.[2]
Riešenie
Veta: Neorientovaný graf má uzavretý Eulerovský ťah práve vtedy ak je súvislý a ak platí
Veta: Ak je súvislý, neorientovaný graf ktorý obsahuje práve 2 vrcholy pre ktoré platí 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
- ↑ KOLÁŘ J., 2004, Teoretická informatika, Praha, Česká informatická společnost, 2. vydanie, ISBN 80-900853-8-5
- ↑ KNOR M., 2000, KOMBINATORIKA A TEÓRIA GRAFOV I, Univerzita Komenského Bratislava, Vydavateľstvo UK, 1. vydanie, ISBN 80-223-1339-4
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Česko-Slovensko
1736
1926
Algoritmus
Binárny strom (teória grafov)
Cesta (teória grafov)
Chromatické číslo
Chromatický index
Cyklomatické číslo grafu
Diskrétna matematika
Eulerovský ťah
Excentricita (teória grafov)
Faktor grafu
Farbenie grafu
Farbenie vrcholov
Grafová postupnosť
Graf (matematika)
Hamiltonovská kružnica
Hamiltonovský graf
Informatika
Izomorfizmus grafov
Kaliningrad
Komplement grafu
Komponent grafu
Kostra grafu
Kružnica (teória grafov)
Leonhard Euler
Matematika
Minimálna kostra grafu
Most (teória grafov)
Neorientovaný graf
Neplanárny graf
Nezávislá množina
Ohodnotený graf
Oreho veta
Orientované stromy
Orientovaný graf
Otakar Borůvka
Petersenov graf
Podgraf
Pravidelný graf
Priesečníkové číslo (teória grafov)
Problém obchodného cestujúceho
Problém siedmich mostov
Rovinný graf
Súvislý graf
Sled (teória grafov)
Slovensko
Spektrálna teória grafov
Strom (teória grafov)
Teória grafov
Teória grafov – grafová postupnosť
Topologická teória grafov
Vrchol (teória grafov)
Vzdialenosť (teória grafov)
Wikipédia:Výhonok
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk