Hamiltonska vägen - Hamiltonian path

Den här artikeln handlar om karaktären hos Hamiltonian -vägar. För frågan om förekomsten av en Hamiltonian -väg eller -cykel i en given graf, se Hamiltonian path -problem .
En Hamiltonian cyklar runt ett nätverk med sex hörn

I det matematiska fältet grafteori är en Hamiltonisk väg (eller spårbar väg ) en sökväg i en oriktad eller riktad graf som besöker varje hörn exakt en gång. En Hamiltonian cykel (eller Hamiltonian krets ) är en Hamiltonian väg som är en cykel . Att avgöra om sådana vägar och cykler finns i grafer är det Hamiltonianska vägproblemet , som är NP-komplett .

Hamiltonianska vägar och cykler är uppkallade efter William Rowan Hamilton som uppfann det icosian -spelet , nu också känt som Hamiltons pussel , vilket innebär att man hittar en Hamiltonian -cykel i dodekaederns kantgraf . Hamilton löste detta problem med hjälp av icosian calculus , en algebraisk struktur baserad på enhetens rötter med många likheter med kvartarna (också uppfunnet av Hamilton). Denna lösning generaliserar inte till godtyckliga grafer.

Trots att de är uppkallade efter Hamilton hade Hamiltonian cykler i polyeder också studerats ett år tidigare av Thomas Kirkman , som i synnerhet gav ett exempel på en polyhedron utan Hamiltonian cykler. Ännu tidigare, Hamiltons cykler och stigar i riddar grafen av schackbrädet , den riddare turné , varit hade studerat i den 9: e-talet i indiska matematik av Rudrata och ungefär samtidigt i islamiska matematik genom al-ADLI ar-Rumi . I 1700 -talets Europa publicerades riddarturer av Abraham de Moivre och Leonhard Euler .

Definitioner

En Hamiltonian -väg eller spårbar väg är en väg som besöker varje toppunkt i grafen exakt en gång. En graf som innehåller en hamiltons väg kallas en spårbar graf . En graf är Hamilton-ansluten om det för varje par hörn finns en hamiltons väg mellan de två hörnen.

En Hamiltonian -cykel , Hamilton -krets , toppunktstur eller grafcykel är en cykel som besöker varje toppunkt exakt en gång. En graf som innehåller en Hamiltonsk cykel kallas en Hamiltonian graf .

Liknande begrepp kan definieras för riktade grafer , där varje kant (båge) av en väg eller cykel endast kan spåras i en enda riktning (dvs hörnen är förbundna med pilar och kanterna spåras "svans-till-huvud").

En Hamiltonisk sönderdelning är en kantnedbrytning av en graf i Hamiltoniska kretsar.

En Hamilton -labyrint är en typ av logikpussel där målet är att hitta den unika Hamiltonian -cykeln i en given graf.

Exempel

Ortografiska projektioner och Schlegel -diagram med Hamiltoniska cykler av hörnen för de fem platoniska fasta ämnena - bara oktahedronen har en eulerisk väg eller cykel genom att förlänga sin väg med den prickade

Egenskaper

Den Herschel grafen är den minsta möjliga polyhedral graf som inte har en Hamiltonian cykel. En möjlig Hamilton -väg visas.

Varje Hamiltonian cykel kan konverteras till en Hamiltonian sökväg genom att ta bort en av dess kanter, men en Hamiltonian sökväg kan bara förlängas till Hamilton cykel endast om dess slutpunkter ligger intill.

Alla Hamiltonian -grafer är tvåkopplade , men en dubbelkopplad graf behöver inte vara Hamiltonian (se till exempel Petersen -grafen ).

En Eulerian -graf G (en ansluten graf där varje toppunkt har jämn grad) har nödvändigtvis en Euler -rundtur, en stängd promenad som passerar genom varje kant av G exakt en gång. Denna turné motsvarar en Hamiltonisk cykel i linjediagrammet L ( G ), så linjediagrammet för varje Eulerian -graf är Hamiltonian. Linjediagram kan ha andra Hamiltonian -cykler som inte motsvarar Euler -turer, och särskilt linjediagrammet L ( G ) för varje Hamiltonian -graf G är själv Hamilton, oavsett om grafen G är Eulerian.

En turnering (med mer än två hörn) är Hamilton om och bara om den är starkt ansluten .

Antalet olika Hamiltoniska cykler i en komplett oriktad graf på n hörn är och i en komplett riktad graf på n hörn är . Dessa räkningar antar att cykler som är desamma bortsett från deras utgångspunkt inte räknas separat.

Bondy – Chvátal sats

Den bästa vertex grad karakterisering av Hamiltonian grafer lämnades i 1972 av Bondy - Chvatal sats, som generaliserar tidigare resultat av GA Dirac (1952) och Øystein Ore . Både Diracs och Ores satser kan också härledas från Pósas sats (1962). Hamiltonicity har studerats ingående med avseende på olika parametrar, såsom graf densitet , seghet , förbjudna subgrafer och avstånd bland andra parametrar. Dirac och Ores satser anger i princip att en graf är Hamiltonian om den har tillräckligt med kanter .

Bondy – Chvátal -satsen fungerar på stängningskl ( G ) i en graf G med n hörn, erhållen genom att upprepade gånger lägga till en ny kant uv som förbinder ett icke -angränsande par hörn u och v med deg ( v ) + deg ( u ) ≥ n tills inga fler par med den här egenskapen kan hittas.

Bondy – Chvátal Theorem (1976). En graf är Hamiltonian om och endast om dess stängning är Hamiltonian.

Eftersom kompletta grafer är Hamiltoniska, är alla grafer vars stängning är fullständiga Hamiltonian, vilket är innehållet i följande tidigare satser av Dirac och Ore.

Dirac's sats (1952). En enkel graf med n hörn ( ) är Hamiltonian om varje toppunkt har grad eller högre.
Malmteorem (1960). En enkel graf med n hörn () är Hamiltonian om summan av deras grader är för varje par icke-intilliggande hörn n eller större.

Följande satser kan betraktas som riktade versioner:

Ghouila-Houiri (1960). En starkt ansluten enkelriktad graf med n hörn är Hamiltonian om varje toppunkt har en hel grad större än eller lika med n .
Meyniel (1973). En starkt ansluten enkelriktad graf med n hörn är Hamiltonian om summan av fulla grader för varje par distinkta icke-intilliggande hörn är större än eller lika med .

Antalet hörn måste fördubblas eftersom varje oriktad kant motsvarar två riktade bågar och därmed är graden av en toppunkt i den riktade grafen dubbelt så hög som graden i den oriktade grafen.

Rahman– Kaykobad (2005). En enkel graf med n hörn har en Hamiltonisk väg om summan av deras grader och deras kortaste väglängd är större än n för varje icke-intilliggande hörnpar .

Satsen ovan kan bara erkänna förekomsten av en hamiltonisk väg i ett diagram och inte en Hamiltonisk cykel.

Många av dessa resultat har analoger för balanserade bipartitgrafer , där toppunktsgraderna jämförs med antalet hörn på en enda sida av tvåpartiet snarare än antalet hörn i hela grafen.

Förekomst av Hamiltoniska cykler i plana grafer

Satsning (Whitney, 1931). En 4-ansluten plan triangulering har en Hamiltonisk cykel.
Sats (Tutte, 1956). En 4-ansluten plan graf har en Hamiltonian cykel.

Det Hamiltoniska cykelpolynomet

En algebraisk framställning av de Hamiltoniska cyklerna för en given vägd digraph (vars bågar tilldelas vikter från ett visst markfält) är Hamilton -cykelpolynomet för dess viktade adjacensmatris definierad som summan av produkterna från bågvikterna för digraphs Hamiltonian -cykler . Detta polynom är inte identiskt noll som en funktion i bågvikterna om och bara om digrafen är Hamiltonian. Förhållandet mellan beräkningskomplexiteten att beräkna det och beräkna det permanenta visades av Grigoriy Kogan.

Se även

Anteckningar

Referenser

externa länkar