Obsah ⇫

• hamiltonovský graf, hamiltonovská kružnice, hamiltonovská cesta
• příklady hamiltonovských a nehamiltonovských grafů
• postačující podmínky k určování hamiltonovského grafu
• algoritmus pro hledání hamiltonovské kružnice
• základní pravidla pro hledání hamiltonovské kružnice

Teorie ⇫

Název grafu se vztahuje ke jménu irského matematika Sira Williama Rowana Hamiltona, který vymyslel v roce 1857 hru, skládající se z pravidelného 12-ti stěnu (obr.1) a 20-ti kolíků. Každý kolík byl umístěn v jednom rohu 12-ti stěnu (tj. v každém vrcholu) a byl označen jménem důležitého hlavního města Evropy. Úkolem hráče bylo najít cestu procházející všechna města, každé právě jednou, a vrátit se zpět do města, z kterého vyšel. Pro přehlednost byl na každém kolíku provázek, který hráč spojil vždy s následujícím kolíkem, v pořadí, jakým města procházel.

Obr.1 Hamiltonovský graf

Příklady grafů, které nejsou hamiltonovské:

Příklady grafů, které jsou hamiltonovské:

Rozhodnout, zda je graf hamiltonovský, není vždy snadné. Dosud totiž není známa žádná jednoduchá nutná a postačující podmínka k tomu, aby graf byl hamiltonovský. Je známo několik postačujících podmínek k hamiltonovskosti grafu:

Věta 1 (Dirac, 1952):

Nechť graf G je n-vrcholový, n≥3, stupeň každého vrcholu je alespoň $\frac{n}{2}$ , pak G je hamiltonovský.

Věta 2 (Ore, 1960):

Nechť G je n-vrcholový graf, n≥3, a nechť pro každou dvojicí nesousedních vrcholů u a v platí: degGu+degGv≥n,pak G je hamiltonovský.

Nutnou podmínku dává následující věta:

Věta 3:

Nechť G=(V,E) je hamiltonovský graf, S nechť je neprázdná vlastní podmnožina vrcholové množiny V a nechť c(G-S) je počet komponent grafu G-S, pak platí: c(G-S)≤|S|.

Graf G je hamiltovský, hamiltonovka je v grafu vyznačená barevně.

Důsledek:

Graf Kr,s je hamiltonovský právě tehdy, když r = s.

Poznámka: Opačné tvrzení k Větě 3 neplatí. Viz následující příklad.

Petersenův graf není hamiltonovský, i když pro každou jeho podmnožinu S množiny jeho vrcholů platí tvrzení z Věty 3.

Poznámka: Větu 3 můžeme použít jenom k důkazu, že graf není hamiltonovský. Když najdeme v grafu jedinou vlastní podmnožinu vrcholů, pro kterou neplatí vztah z Věty1, tak můžeme prohlásit, že graf není hamiltovoský. Když pro všechny vlastní podmnožiny platí vztah z Věty1, tak graf může i nemusí být hamiltonovský.

Základní typ algoritmu pro hledání hamiltonovské cesty:

Vezmeme cestu x0, x1, …, xk ve zkoumaném grafu, kterou se pokoušíme prodloužit na hledanou cestu nebo kružnici postupným přidáváním hran vedoucích z koncového vrcholu do ještě nepoužitých vrcholů. Pokud takové prodloužení neexistuje, zkrátíme cestu x1, …, xk a snažíme se prodloužení určit jiným způsobem. Výpočet končí ve chvíli, kdy je buď nalezeno požadované řešení, nebo se neúspěšně proberou všechny možnosti prodlužování.

Typy hamiltonovských úloh

Úlohy, ve kterých jde o hamiltonovské pojmy, mají mnoho variant a lze je třídit z několika různých hledisek. Rozlišujeme existenční a optimalizační úlohy. V existenčních úlohách jde o zjištění existence nebo dokonce o nalezení hamiltonovské cesty, kružnice nebo cyklu v daném grafu. V optimalizačních úlohách jsou hrany grafu ohodnoceny délkami a požaduje se nalezení hamiltonovské cesty, kružnice nebo cyklu o nejmenší délce. Dále úlohy dělíme na orientované a neorientované podle toho, zda hledáme orientovanou nebo neorientovanou hamiltonovskou cestu, případně zda hledáme hamiltonovský cyklus nebo kružnici. V případě hamiltonovských cest musíme navíc rozlišit tři až čtyři varianty podle toho, zda je v zadání úlohy předepsán vrchol, ve kterém musí hamiltonovská cesta začínat, a vrchol, kde musí končit. Všechny výše uvedené typy hamiltonovských úloh jsou pro obecné grafy NP – těžké (tj. neexistuje pro úlohu algoritmus, který by jí řešil v polynomiálním čase).

Uvedeme základní pravidla pro hledání hamiltonovské kružnice v daném malém grafu:

1. Má-li daný graf n vrcholů, pak hamiltonovská kružnice má právě n hran.
2. Jestliže vrchol v má stupeň k, pak hamiltonovská kružnice musí obsahovat právě dvě hrany incidentní s vrcholem v.
3. Při konstrukci hamiltonovské kružnice nemůže být vytvořena kružnice, která by neobsahovala všechny vrcholy daného grafu.
4. Jakmile hamiltonovská kružnice, kterou konstruujeme, prochází vrcholem v, pak ostatní nepoužité hrany incidentní s vrcholem v můžeme vyloučit (tyto již v hamiltonovské kružnici ležet nebudou).

Řešený příklad ⇫

1. Rozhodněte, zda následující graf obsahuje hamiltonovskou kružnici, či nikoli.

Krok 1

Krok 2

2. Rozhodněte, zda následující graf je hamiltonovský?

Krok 1

Krok 2

Krok 3

Tentokrát graf splňuje všechny tři věty.

Úlohy k řešení ⇫

1. Najděte v grafech na obrázku hamiltonovskou kružnici (existuje jich více).

2. Dokažte sporem tvrzení:

Jestliže v grafu G existuje most, pak v grafu G neexistuje hamiltonovská kružnice. (nejprve správně zformulujte tvrzení pro důkaz sporem!)

Zdroje textů

1. DIMA - diskrétní matematika, http://oliva.uhk.cz
2. Hliněný, Petr. Diskrétní Matematika (456-533 DIM), 2006
3. Kovář, Petr. DISKRÉTNÍ MATEMATIKA a ÚVOD DO TEORIE GRAFŮ ( příklady k procvičení ), 2012
4. Wikipedia, http://cs.wikipedia.org/wiki/Hamiltonovský_graf