Hamiltonovský graf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Graf, jehož uzly představují vrcholy dvanáctistěnu. Červeně je vyznačena hamiltonova kružnice.

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.

  1. Označme u počet uzlů grafu a předpokládejme, že u ≥ 3. Má-li každý uzel stupeň alespoň ½ u, je graf hamiltonovský.
  2. 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ý.
  3. 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]

HamiltonObr48.GIF 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]

HamiltonObr49.GIF
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]

HamiltonObr51.GIF
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]

Hamiltonovská kružnice

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, A. 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í. Praha, SPN, 1989. 54-00-40/1
  • Nešetřil, J. Teorie grafů.Praha, SNTL, 1979. 04-017-79
  • Arnošt Večerka - Grafy a grafové algoritmy - skripta UPOL [1]