Hamiltongrafer

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif
En hamiltoncykel i ett grafisk representation av Iconsian spelet.

Hamiltongrafer är det gemensamma namnet för grafer som har hamiltoncyklar/vägar i dem. Hamiltonväg är en väg i en graf som innehåller varje hörn (nod, punkt) en gång. En hamiltoncykel är en cykel som innehåller varje hörn en gång och återvänder till samma startpunkt.

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

Innehåll

Historia

Hamiltongrafer är uppkallade efter William Rowan Hamilton som bl.a. uppfann Icosianspelet. Han sålde idéen 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 vilkor 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 anses vara godtyckliga att visa att grafen kan innehålla hamiltoncyklar.

Matematiska Egenskaper

En enkel graf

Definitioner

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

  • En väg inom grafteori är ett ändligt följd av hörn där det finns förbindelse mellan dem i form av s.k. bågar eller kanter. 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 hörnen till resten av grafen kallas hörnens grad. Det betecknas som d(vn) där vn är hörnen. Exempel på grafen till vänster är att hörnen a har grad 2:

d(a) = 2

Den formella definitionen av en hamiltonväg/cykel är som 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 på grafen till vänster är (b, a, f, e, c, d) Ett exempel på en hamiltoncykel på grafen till vänster är (a, b, c, d, e, f, a)

Satser

Ingen hamiltoncykel

Det finns än så länge inget ordentligt sätt att bevisa att det finns en hamiltonväg i en graf. Man kan, åt andra sidan, visa att graf inte har en hamiltoncykel. Detta förklaras av följande sats.

[1] "Låt G vara en enkel graf. Antag att det finns k st hörn v1,v2,...,vk i G sådana att om man tar bort dessa hörn och alla de kanter, som har hörnen som ändpunkter, så får man en graf med minst k + 1 sammanhängande komponenter. Då 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 markerad x och y blir det 2 + 1 osammanhängande delar vilket, enligt satsen visar att grafen inte har några hamiltoncyklar i den.

Det finns satser som anger tillräckligt med vilkor för att det ska finnas en hamiltoncykel. Följande sats bevisades av G. A. Dirac 1952.

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

Att hitta en hamiltoncykel klassas som en NP-komplett problem. Det betyder 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är större beräkningar kan göras på kortare tid. Tillämpningarna är många, t.ex. optimering, geometri och logistik. Hamiltongrafer används inom beräkningar inom turnering och Cayley grafer.[3]

Ett exempel på minst kostande hamiltoncykel

Handelsresandeproblemet

Det är inte alltid intressant att veta om det finns en hamiltoncykel, utan vilken hamiltoncykel kostar minst. Det gör man på grafer som har givna bågkostnader. Se exempel till höger. Detta brukar kallas för ett gemensamt ord; handelsresandeproblemet. Bågkostnader kan representera många olika saker; tid, sträckor, kostnad, osv.

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å storleken av grafen. 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 en heuristik metod.


En grafiskt representation av alla giltiga drag för en springare på en 8 * 8 schackbräda. Siffrorna anger möjliga drag från den punkt.

Springareproblemet

Är det möjligt för springaren i schack att gå på varje ruta exakt en gång på schackbrädan?

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 i 1823 av H. C. Warnsdorff.

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

  1. A. Asratian; A. Björn; B. O. Turesson: Diskret matematik 2008 Matematiska Instutitionen, Linköping
  2. Andrásfai Béla: Introductory Graph Theory 1977 Akadémiai Kiadó, Budapest ISBN 0 85274 249 5
  3. Edited by Alspach B.R.; Godsil C.D. : Cycles in Graphs 1985 Elsevier Science Publishers B.V.

Se även

Externa länkar

Personliga verktyg