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

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ů

Příklad 1

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

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

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

Tři příklady na mřížkovém grafu 8x8

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

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.