Hamiltonova cesta - Hamiltonian path

Tento článek pojednává o povaze hamiltonovských cest. K otázce existence Hamiltonovské dráhy nebo cyklu v daném grafu viz Problém hamiltonovské cesty.
Hamiltonovský cyklus kolem sítě šesti vrcholů

V matematický pole teorie grafů, a Hamiltonova cesta (nebo sledovatelná cesta) je cesta v neorientovaném nebo směrovaném grafu, který každého navštíví vrchol přesně jednou. A Hamiltonovský cyklus (nebo Hamiltonovský okruh) je hamiltonovská cesta, která je a cyklus. Určení, zda takové cesty a cykly existují v grafech, je Problém hamiltonovské cesty, který je NP-kompletní.

Hamiltonovské cesty a cykly jsou pojmenovány po William Rowan Hamilton kdo vynalezl icosian hra, nyní také známý jako Hamiltonova hádanka, což zahrnuje nalezení Hamiltonovského cyklu v hranovém grafu dvanáctistěn. Hamilton tento problém vyřešil pomocí ikosiánský počet, an algebraická struktura na základě kořeny jednoty s mnoha podobnostmi s čtveřice (také vynalezl Hamilton). Toto řešení nezobecňuje na libovolné grafy.

Navzdory tomu, že byl pojmenován po Hamiltonovi, byly o rok dříve studovány Hamiltonovské cykly v mnohostěnách Thomas Kirkman, který zejména uvedl příklad mnohostěnu bez Hamiltonovských cyklů.[1] Ještě dříve, Hamiltonovské cykly a cesty v rytířský graf z šachovnice, rytířské turné, byl studován v 9. století v Indická matematika podle Rudrata a přibližně ve stejnou dobu v Islámská matematika podle al-Adli ar-Rumi. V Evropě 18. století vydával rytířské zájezdy Abraham de Moivre a Leonhard Euler.[2]

Definice

A Hamiltonova cesta nebo sledovatelná cesta je cesta který navštíví každý vrchol grafu přesně jednou. Graf, který obsahuje hamiltonovskou cestu, se nazývá a sledovatelný graf. Graf je Hamiltonian připojený pokud pro každou dvojici vrcholů existuje Hamiltonova cesta mezi dvěma vrcholy.

A Hamiltonovský cyklus, Hamiltonovský okruh, vrchol turné nebo grafový cyklus je cyklus který navštíví každý vrchol přesně jednou. Graf, který obsahuje hamiltonovský cyklus, se nazývá a Hamiltonovský graf.

Podobné pojmy mohou být definovány pro řízené grafy, kde lze každou hranu (oblouk) cesty nebo cyklu sledovat pouze v jednom směru (tj. vrcholy jsou spojeny šipkami a hrany jsou sledovány „od ocasu k hlavě“).

A Hamiltoniánský rozklad je okrajový rozklad grafu na hamiltonovské obvody.

A Hamiltonské bludiště je typ logické hádanky, ve které je cílem najít jedinečný hamiltonovský cyklus v daném grafu.[3][4]

Příklady

Jeden možný Hamiltonovský cyklus skrz každý vrchol a dvanáctistěn je zobrazen červeně - jako všechny platonické pevné látky, dodecahedron je Hamiltonian
Výše uvedené jako dvourozměrný rovinný graf

Vlastnosti

The Herschelův graf je nejmenší možný polyedrický graf který nemá hamiltonovský cyklus. Je zobrazena možná hamiltonovská cesta.

Jakýkoli Hamiltonovský cyklus lze převést na Hamiltonovu cestu odstraněním jedné z jeho hran, ale Hamiltonovu cestu lze rozšířit na Hamiltonovský cyklus pouze v případě, že jeho koncové body sousedí.

Všechny Hamiltonovské grafy jsou propojené, ale biconnected graf nemusí být Hamiltonian (viz například Petersenův graf ).[6]

An Euleriánský graf G (A připojený graf ve kterém má každý vrchol rovnoměrný stupeň) nutně má Eulerovu prohlídku, uzavřenou procházku procházející každou hranou G přesně jednou. Tato prohlídka odpovídá Hamiltonovskému cyklu v hranový graf L(G), takže spojnicový graf každého euleriánského grafu je hamiltoniánský. Čárové grafy mohou mít další hamiltonovské cykly, které neodpovídají Eulerovým prohlídkám, zejména pak spojnicový graf L(G) každého Hamiltonovského grafu G je sám o sobě Hamiltonian, bez ohledu na to, zda je graf G je Eulerian.[7]

A turnaj (s více než dvěma vrcholy) je Hamiltonian právě tehdy, když je silně propojený.

Počet různých hamiltonovských cyklů v úplném neorientovaném grafu n vrcholy je (n − 1)! / 2 a v úplném orientovaném grafu n vrcholy je (n − 1)!. Tyto počty předpokládají, že cykly, které jsou stejné kromě jejich počátečního bodu, se nepočítají samostatně.

Bondy – Chvátalova věta

Nejlepší vrchol stupeň charakterizaci hamiltonovských grafů poskytla v roce 1972 Bondy –Chvátal věta, která zobecňuje dřívější výsledky podle G. A. Dirac (1952) a Øystein Ore. Diracova i Oreova věta lze také odvodit z Pósova věta (1962). Hamiltonicita byla široce studována ve vztahu k různým parametrům, jako je graf hustota, houževnatost, zakázané podgrafy a vzdálenost mimo jiné parametry.[8] Věty Diraca a Ore v podstatě uvádějí, že graf je hamiltoniánský, pokud má dost hran.

Bondy – Chvátalova věta funguje na uzavření cl (G) grafu G s n vrcholy, získané opakovaným přidáváním nové hrany uv připojení a nesousedící dvojice vrcholů u a proti s deg (proti) + stupeň (u) ≥ n dokud nelze najít další páry s touto vlastností.

Bondy – Chvátalova věta (1976). Graf je hamiltoniánský, právě když je jeho uzavření hamiltoniánský.

Jelikož jsou úplné grafy hamiltoniánské, všechny grafy, jejichž uzavření je kompletní, jsou hamiltoniánské, což je obsah následujících dřívějších vět Diraca a Ore.

Diracova věta (1952). A jednoduchý graf s n vrcholy (n ≥ 3) je hamiltonián, pokud má každý vrchol titul nebo vyšší.
Oreova věta (1960). A jednoduchý graf s n vrcholy (n ≥ 3) je hamiltonián, pokud pro každou dvojici nesousedících vrcholů je součet jejich stupňů n nebo vyšší.

Následující věty lze považovat za řízené verze:

Ghouila-Houiri (1960). A silně propojený jednoduchý řízený graf s n vertices je hamiltonián, pokud má každý vrchol plný stupeň větší nebo rovnýn.
Meyniel (1973). A silně propojený jednoduchý řízený graf s n vertices je hamiltonián, pokud je součet celých stupňů každé dvojice odlišných nesousedících vrcholů větší nebo roven 2n − 1.

Počet vrcholů musí být zdvojnásoben, protože každá neorientovaná hrana odpovídá dvěma směrovaným obloukům, a proto je stupeň vrcholu v směrovaném grafu dvojnásobkem stupně v neorientovaném grafu.

Rahman -Kaykobad (2005). A jednoduchý graf s n vrcholy mají hamiltonovskou cestu, pokud je pro každé nesousedící vrcholové páry součet jejich stupňů a jejich nejkratší délka cesty větší než n.[9]

Výše uvedená věta dokáže rozpoznat pouze existenci Hamiltonovské cesty v grafu a nikoli Hamiltonovského cyklu.

Mnoho z těchto výsledků má analogie pro vyvážené bipartitní grafy, ve kterém jsou stupně vrcholů porovnány s počtem vrcholů na jedné straně bipartice spíše než s počtem vrcholů v celém grafu.[10]

Existence hamiltonovských cyklů v rovinných grafech

Věta (Whitney, 1931)
4-spojená planární triangulace má hamiltonovský cyklus.
Věta (Tutte, 1956)
4-spojený rovinný graf má hamiltonovský cyklus.

Hamiltonovský cyklický polynom

Algebraické znázornění hamiltonovských cyklů daného váženého digrafu (jehož obloukům jsou přiřazeny váhy z určitého pozemního pole) je Hamiltoniánský polynom jeho vážené matice sousedství definované jako součet součinů hmotnosti oblouku Hamiltonových cyklů digrafu. Tento polynom není identicky nulový jako funkce v obloukových vahách právě tehdy, pokud je digrafem hamiltonián. Vztah mezi výpočetní složitostí jeho výpočtu a výpočet trvalé byl zobrazen v Kogan (1996).

Viz také

Poznámky

  1. ^ Biggs, N. L. (1981), "T. P. Kirkman, matematik", Bulletin of London Mathematical Society, 13 (2): 97–120, doi:10.1112 / blms / 13.2.97, PAN  0608093.
  2. ^ Watkins, John J. (2004), „Kapitola 2: Rytířské prohlídky“, Obecně: Matematika problémů šachovnice, Princeton University Press, s. 25–38, ISBN  978-0-691-15498-5.
  3. ^ de Ruiter, Johan (2017). Hamilton Mazes - Průvodce pro začátečníky.
  4. ^ Friedman, Erich (2009). „Hamiltonovské bludiště“. Erich's Puzzle Palace. Archivováno z původního dne 16. dubna 2016. Citováno 27. května 2017.
  5. ^ Gardner, M. „Matematické hry: O pozoruhodné podobnosti mezi ikonickou hrou a věžími v Hanoji.“ Sci. Amer. 196, 150–156, květen 1957
  6. ^ Eric Weinstein. „Biconnected Graph“. Wolfram MathWorld.
  7. ^ Balakrishnan, R .; Ranganathan, K. (2012), „Corollary 6.5.5“, Učebnice teorie grafů, Springer, str. 134, ISBN  9781461445296.
  8. ^ Gould, Ronald J. (8. července 2002). „Pokroky v hamiltonovském problému - průzkum“ (PDF). Emory University. Citováno 2012-12-10.
  9. ^ Rahman, M. S .; Kaykobad, M. (duben 2005). "Na Hamiltonových cyklech a Hamiltonových cestách". Dopisy o zpracování informací. 94: 37–41. doi:10.1016 / j.ipl.2004.12.002.
  10. ^ Moon, J .; Moser, L. (1963), „O Hamiltonových bipartitních grafech“, Israel Journal of Mathematics, 1 (3): 163–165, doi:10.1007 / BF02759704, PAN  0161332

Reference

externí odkazy