Hamiltongraf

En Hamiltongraf är inom matematik en graf som har en Hamiltoncykel. En Hamiltonväg är en väg i en graf som innehåller varje nod exakt en gång. En Hamiltoncykel är en Hamiltonväg som börjar och slutar i samma nod.

Hamiltongrafer har många tillämpningar, bl.a. handelsresandeproblemet och springareproblemet.

Historia

Hamiltongrafer är uppkallade efter William Rowan Hamilton som bl.a. uppfann Icosianspelet. Han sålde idén vidare till en leksaksaffärsman i Dublin. Hamilton löste detta problem med hjälp av vad han kallade "Icosian calculus". Frågan som återstod var, vilka villkor krävs det för att en graf ska ha en hamiltoncykel? Än så länge finns det inget fullständigt sätt att bevisa att det finns en hamiltoncykel i en graf. Men det finns satser som ger tillräckliga villkor för att en graf ska innehålla Hamiltoncykler.

Matematiska egenskaper

Definitioner

Först följer några definitioner inom grafteori och sedan några intressanta satser gällande Hamiltoncykler.

• En väg inom grafteori är en ändlig följd av hörn med förbindelse mellan sig i form av s.k. bågar. I grafen till vänster är ett exempel på en väg (a , f, e , c).
• En cykel är en väg som kommer tillbaks till startpunkten. Ett exempel på grafen till vänster är (c, d, e, c)
• Antalet kanter som förbinder ett hörn till resten av grafen kallas hörnets grad. Det betecknas som ${\displaystyle d(v_{n})}$ där ${\displaystyle v_{n}}$ är hörnen. Exempel på grafen till vänster är att hörnen a har grad 2:

${\displaystyle d(a)=2}$

Den formella definitionen av en Hamiltonväg eller -cykel är följande:

Låt G vara en graf med fler än 2 hörn. Vi säger att grafen G har en Hamiltonväg/cykel om det finns en väg/cykel som omfattar alla hörnen i grafen.

Ett exempel på en Hamiltonväg i grafen till vänster är (b, a, f, e, c, d), och ett exempel på en Hamiltoncykel är (a, b, c, d, e, f, a)

Satser

Det finns än så länge inget ordentligt sätt att bevisa att det finns en Hamiltonväg i en graf. Man kan däremot visa att en graf inte har en hamiltoncykel:

Om G är en enkel graf med k hörn betecknade ${\displaystyle v_{1},v_{2},...,v_{k}}$ sådana att om man tar bort något av dessa hörn och alla de kanter som har hörnen som ändpunkter, så får man en graf med minst ${\displaystyle k+1}$ sammanhängande komponenter så kan inte G innehålla någon Hamiltoncykel.^[1]

Ett exempel på föregående sats är grafen till höger. Om man tar bort hörnen markerade som x och y blir det 2 + 1 osammanhängande delar, vilket enligt satsen visar att grafen inte har några Hamiltoncykler i sig.

Det finns satser som anger tillräckliga villkor för att det ska finnas en Hamiltoncykel. Följande sats bevisades av G. A. Dirac 1952.

Låt G vara en enkel graf med ${\displaystyle n\geq 3}$ hörn. Om graden av varje hörn är minst ${\displaystyle {\frac {n}{2}}}$ innehåller grafen en Hamiltoncykel.^[2]

Att hitta en Hamiltoncykel är ett NP-fullständigt problem, vilket innebär att lösningen kan vara väldigt tidskrävande om man jobbar med stora grafer.

Tillämpningar

Hamiltongrafer har fått en större betydelse med datorns tillkomst då större beräkningar kan göras på kortare tid. Tillämpningarna är många, exempelvis optimering, geometri och logistik. Hamiltongrafer används inom beräkningar inom turnering och Cayleygrafer.^[3]

Handelsresandeproblemet

Det är inte alltid intressant att veta om det finns en hamiltoncykel, utan vilken hamiltoncykel som är billigast på en graf som har givna bågkostnader. Detta brukar kallas för handelsresandeproblemet. Bågkostnader kan representera många olika saker; tid, sträcka, kostnad.

Det är oftast svårt att hitta den minsta kostnaden för en cykel eftersom sökandet kan bli väldigt tidskrävande beroende på grafens storlek. Man har istället utformat algoritmer som kan hitta någon cykel, vilket går betydligt fortare, men man vet inte om det faktiskt är den kortaste vägen eller inte. Detta kallas för en heuristisk metod.

Springareproblemet

Springareproblemet behandlar frågan "Är det möjligt för springaren i schack att gå på varje ruta exakt en gång på schackbrädet?"

Detta är en fråga från antiken som klassas som en svår uppgift. Den första algoritmen för att lösa springareproblemet var Warnsdorffs algoritm från 1823.

En enkel sammanfattning av Warnsdorffs lösning är att det gäller att välja den rutan som har så få drag från den som möjligt. Detta är för att inte skapa en återvändsgränd så att springaren inte kan gå på någon annan rutan än den, den har redan gått på.

Källor

Externa länkar

• WolframMathworld
• Account of the Icosian Calculus
• Warnsdorffs Algoritm