graf obsahující Hamiltonovskou kružnici From Wikipedia, the free encyclopedia
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.
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.
K tomu, aby byl graf s u ≥ 3 uzly hamiltonovský, tedy stačí splnění některé z následujících podmínek:
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). |
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ý.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.