Články
Procházky po cestách a místech
Eulerovské a Hamiltonovské grafy jsou zábavné.
Představte si, že jste poštovní doručovatel, který musí obejít všechny ulice ve městě, nebo plánovač tras, který potřebuje navštívit každou pobočku firmy přesně jednou. Na první pohled jde o běžné logistické úlohy. V matematice však tyto problémy otevírají fascinující svět teorie grafů, mezi něž patří Eulerovské a Hamiltonovské grafy. I když oba pracují s pojmem cesta, jejich pravidla jsou odlišná a vedou k úplně jiným matematickým dobrodružstvím.
Eulerovské grafy - mistři cest
Příběh Eulerovských grafů začíná v 18. toletí v Königsbergu (dnešní Kaliningrad). Městem protékala řeka s ostrovy propojenými sedmi mosty. Obyvatelé se snažili vyřešit hádanku: je možné přejít všech sedm mostů právě jednou a vrátit se na začátek?
Slavný matematik Leonhard Euler dokázal, že to nejde. Položil tím základy teorie grafů. Eulerovský graf je takový graf, ve kterém existuje Eulerovský tah. To je cesta, která projde každou hranu grafu právě jednou.
Euler přišel na elegantní pravidlo: aby byl graf eulerovský, musí být souvislý a každý jeho vrchol musí mít sudý stupeň (tedy musí do něj vstupovat a vystupovat sudý počet hran). Pokud má graf jen dva vrcholy s lichým stupněm, lze vytvořit Eulerovskou cestu (začínající v jednom lichém a končící ve druhém), ale ne uzavřený cyklus.
Hamiltonovské grafy - návštěvníci míst
Zatímco Euler se soustředil na hrany (cesty/ulice), irský matematik William Rowan Hamilton obrátil pozornost k vrcholům (místům/městům).
Hamiltonovský graf obsahuje Hamiltonovskou kružnici. To je cesta, která projde každý vrchol grafu právě jednou a vrátí se do výchozího bodu. Možná vás napadne, že to musí být podobně snadné jako u Eulera. Omyl! Zatímco pro Eulerovské grafy máme jednoduché pravidlo o sudosti vrcholů, pro Hamiltonovské grafy neexistuje žádná snadná a obecná podmínka, jak je na první pohled poznat.
Tento problém je srdcem informatiky. Problém hledání Hamiltonovské kružnice patří mezi tzv. NP-úplné problémy. To znamená, že s rostoucím počtem vrcholů roste čas potřebný k nalezení řešení tak extrémně rychle, že i ty nejvýkonnější počítače světa se při větších grafech mohou "zapotit".
Možná si říkáte: "hezká teorie, ale k čemu mi to je?" Odpověď je všude kolem nás. Kdykoliv plánujete trasu svozu odpadu, efektivní cestu pro tiskárnu s 3D tiskem nebo dokonce optimalizujete trasu pro logistické drony, podvědomě pracujete s těmito koncepty. Eulerovské grafy nám pomáhají kreslit jedním tahem, zatímco Hamiltonovské grafy řeší slavný "problém obchodního cestujícího", kde je cílem navštívit všechna města při co nejnižších nákladech.
>>>>>
31-05-2026