Hamiltonovská kružnice - Encyklopedie - Portál divoch.net

Hledat:

Invia.cz Pojeďte do Egypta Kanárské ostrovy Dovolená - Turecko Dominikánská republika Madeira Last minute
 

Hamiltonovský graf

(Přesměrováno z Hamiltonovská kružnice, přímý odkaz na Hamiltonovský graf)
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:

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]

 
Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/w/index.php?title=Hamiltonovský_graf&oldid=9899067#Hamiltonovsk.C3.A1_kru.C5.BEnice
Stránka byla naposledy upravena 11. 3. 2013 v 10:55. Editovat celý článek Hamiltonovská kružnice.
Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci 3.0 Unported, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.
Další služby: Portál | Katalog | Hledej | Zprávy | Počasí | Kurzy | Práce | Slovník | TV | Online hry | Java hry | SMS | Loga a melodie | Chat | Fórum | Kontakt | Set-top-boxy