Hamiltonovský graf
Hamiltonovský graf je graf, který lze projít takovou cestou, že každý jeho uzel je navštíven právě jednou s výjimkou uzlu výchozího, který je zároveň uzlem cílovým. Neboli – graf je hamiltonovský, právě když obsahuje kružnici, která prochází všemi jeho uzly (tzv. hamiltonovská kružnice). Název připomíná irského matematika a fyzika W. R. Hamiltona (1805–1865), od kterého pocházel hlavolam, v němž bylo za úkol obejít po hranách vrcholy pravidelného dvanáctistěnu.
Postačující podmínky hamiltonovského grafu[editovat | editovat zdroj]
Ačkoliv se hamiltonovské grafy zdají být obdobou eulerovských grafů, 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 však známo několik postačujících podmínek k hamiltonovskosti grafu.
- Označme u počet uzlů grafu a předpokládejme, že u ≥ 3. Má-li každý uzel stupeň (tj. počet hran, které do daného uzlu zasahují) alespoň ½ u, je graf hamiltonovský.
- Označme u počet uzlů grafu a předpokládejme, že u ≥ 3. Je-li pro každou dvojici uzlů, které nejsou spojeny hranou, součet jejich stupňů alespoň u, pak je graf hamiltonovský.
- Označme u počet uzlů grafu a předpokládejme, že u ≥ 3. Jestliže pro každé přirozené číslo k < ½ u je počet uzlů, jejichž stupeň nepřevyšuje k, menší než k, pak je graf hamiltonovský.
K tomu, aby byl graf s u ≥ 3 uzly hamiltonovský, tedy stačí splnění některé z následujících podmínek:
- Každý uzel má stupeň alespoň ½ u. (Diracova podmínka)
- Každá dvojice uzlů nespojených hranou má součet stupňů alespoň u. (Oreho podmínka)
- Pro každé přirozené číslo k < ½ u je počet uzlů, jejichž stupeň nepřevyšuje k, menší než k. (Pósova podmínka)
Příklady hamiltonovských grafů[editovat | editovat zdroj]
Příklad 1[editovat | editovat zdroj]
|
Graf na obrázku nesplňuje Diracovu podmínku (obsahuje uzel 2. stupně, přičemž 2 < 5/2). Splňuje Oreho podmínku (součet stupňů libovolných dvou nespojených uzlů je alespoň 5). Je tedy podle výše uvedených podmínek hamiltonovský. Tento graf splňuje i Pósovu podmínku (počet uzlů stupně 1 je menší než 1, počet uzlů stupně 1 a 2 je menší než 2). |
Příklad 2[editovat | editovat zdroj]
 |
Graf na obrázku nesplňuje Oreho podmínku (obsahuje nespojené uzly 2. a 3. stupně, přičemž 2+3 < 7) ani Diracovu podmínku. Splňuje Pósovu podmínku (počet uzlů 1. stupně je menší než 1, počet uzlů 1. a 2. stupně je menší než 3), a je tedy hamiltonovský. |
Příklad 3[editovat | editovat zdroj]
 |
Graf na obrázku splňuje Diracovu podmínku, neboť každý jeho uzel má stupeň alespoň 3 a splňuje i podmínku Oreho, neboť každé dva uzly nespojené hranou mají součet stupňů alespoň 6. A konečně splňuje i Pósovu podmínku, neboť v něm nejsou žádné uzly stupně menšího než 3. |
Hamiltonovská kružnice[editovat | editovat zdroj]
V teorii grafů je hamiltonovská kružnice (také hamiltonovský cyklus) grafu taková kružnice v tomto grafu, která projde právě jednou všemi jeho vrcholy. Graf, který obsahuje hamiltonskou kružnici, se nazývá Hamiltonovský graf. Hamiltonovská cesta je taková cesta v daném grafu, která prochází každým jeho vrcholem právě jednou.
Každý graf nemusí mít nutně hamiltonovskou kružnici. Nutnými (avšak nikoli postačujícími) podmínkami je, že graf musí být souvislý a každý vrchol musí mít stupeň nejméně rovný dvěma (ke každému vrcholu musí vést alespoň 2 hrany).
Problém nalezení hamiltonovské kružnice je NP-úplný.
Literatura[editovat | editovat zdroj]
- VRBA, Antonín. Grafy : pro III. ročník tříd gymnázií se zaměřením na matematiku, na matematiku a fyziku a pro seminář a cvičení z matematiky ve IV. ročníku gymnázií. 1. vyd. Praha: Státní pedagogické nakladatelství, 1989.
- NEŠETŘIL, Jaroslav. Teorie grafů. 1. vyd. Praha: SNTL, 1979.
- VEČERKA, Arnošt. Grafy a grafové algoritmy - skripta UPOL [online]. Olomouc: Univerzita Palackého, 2007 [cit. 2023-01-07]. Dostupné online.
