Hamilton-veje og Hamilton-kredse forklaret
Tegn fem prikker i en ring, forbind hver med sine to naboer, og du kan gå rundt gennem hver prik én gang og komme hjem: en Hamilton-kreds. Tilføj et par kanter eller fjern nogle, og spørgsmålet bliver overraskende svært. Om en graf har en sådan kreds, er et af de mest kendte problemer, som ingen computer endnu kan besvare hurtigt for enhver graf.
Hvert knudepunkt én gang
En graf er en mængde punkter, knudepunkterne, forbundet af linjer, kanterne. En Hamilton-vej går langs kanter og besøger hvert knudepunkt præcis én gang; en Hamilton-kreds vender desuden tilbage til udgangspunktet, så den har lige så mange kanter som knudepunkter. En graf med en Hamilton-kreds kaldes hamiltonsk. Det er let at tjekke en foreslået rute: tæl knudepunkterne og se på hvert skridt. At finde en, eller vise at der ingen er, er den svære del, for antallet af rækkefølger, knudepunkterne kunne besøges i, vokser som n!, allerede 2,4 × 10¹⁸ for 20 knudepunkter.
Hamiltons ikosiske spil
William Rowan Hamilton, den irske matematiker, der opdagede kvaternionerne, opfandt det ikosiske spil i 1857. Pladen viste et dodekaeder fladtrykt ud i planen, med sine 20 hjørner mærket med konsonanter, og hovedopgaven var at sætte pinde med numrene 1 til 20 på hjørnerne, så på hinanden følgende tal, og 20 og 1, er forbundet med kanter. Hamilton solgte rettighederne for 25 pund til den londonske legetøjsfabrikant John Jaques and Son, som udsendte det i 1859; det solgte dårligt. Gåden har 30 løsninger, når en kreds tælles én gang uanset udgangspunkt og retning. Spørgsmålet selv var ikke nyt: Thomas Kirkman havde i en artikel sendt til Royal Society i 1855 spurgt, hvilke polyedre der har en kreds gennem alle deres hjørner, og havde vist et, der ingen har.
Springerrundture
En springerrundtur flytter en skakspringer, så den lander på hvert felt præcis én gang: en Hamilton-vej i den graf, hvis knudepunkter er felterne, og hvis kanter er springertrækkene. En lukket rundtur ender et springertræk fra sit udgangspunkt, altså en Hamilton-kreds. Skakspillere stillede sådanne opgaver for mere end tusind år siden, og Euler undersøgte dem i en artikel fra 1759. I 1823 foreslog H. C. von Warnsdorff altid at gå til feltet med færrest videre træk; denne enkle regel fuldfører som regel en rundtur på et 8 × 8-bræt uden at gå tilbage. En springer skifter altid feltfarve, så en lukket rundtur kræver lige så mange lyse som mørke felter, hvilket udelukker brætter med et ulige antal felter. Allen Schwenk viste i 1991 præcis, hvilke rektangulære brætter der har en lukket rundtur; blandt de kvadratiske har ethvert med en lige side på 6 eller mere. Det almindelige skakbræt har 13.267.364.410.532 lukkede rundture, talt af Brendan McKay i 1997.
Grafer uden Hamilton-kreds
De hurtigste beviser for, at der ingen kreds er, er optællingsargumenter. Kan knudepunkterne farves med to farver, så hver kant forbinder forskellige farver, skifter en kreds og kræver lige mange knudepunkter af hver farve; et 5 × 5-gitter har 13 af den ene og 12 af den anden, så det har ingen Hamilton-kreds. Et skæreknudepunkt, hvis fjernelse deler grafen, skulle passeres to gange, og et knudepunkt af grad 1 kan slet ikke passeres. Nogle grafer undslipper alle sådanne argumenter. Petersen-grafen, udgivet af Julius Petersen i 1898, har 10 knudepunkter af grad 3 og ingen Hamilton-kreds, og dog efterlader fjernelsen af et vilkårligt knudepunkt en graf, der har en; den er den mindste sådanne hypohamiltonske graf. Herschel-grafen, opkaldt efter Alexander Stewart Herschel, som skrev om det ikosiske spil i 1862, har 11 knudepunkter og 18 kanter og er grafen for et polyeder med ni firkantede flader. Intet polyeder med færre hjørner mangler en Hamilton-kreds. I 1884 formodede Peter Guthrie Tait, at ethvert polyeder med tre kanter i hvert hjørne har en; W. T. Tutte fandt i 1946 et modeksempel med 46 knudepunkter.
Betingelser, der sikrer en
Har en graf mange kanter, er en Hamilton-kreds sikker. Gabriel Dirac beviste i 1952, at en graf med n ≥ 3 knudepunkter, hvor hvert knudepunkt har grad mindst n/2, har en, og Øystein Ore svækkede betingelsen i 1960: det er nok, at to knudepunkter, der ikke er forbundet, altid har grader med sum mindst n. Begge betingelser gælder kun i én retning. En simpel ring af 100 knudepunkter har overalt grad 2, langt under 50, og er alligevel en Hamilton-kreds. Sådan ser billedet ud i almindelighed: der er tilstrækkelige betingelser, og der er grunde til at det slår fejl, og derimellem ligger et stort område af grafer, som kun en søgning kan afgøre.
Hvorfor ingen hurtig test kendes
At afgøre, om en graf har en Hamilton-kreds, er NP-fuldstændigt; det var et af de 21 problemer på Richard Karps liste fra 1972. En metode, der løste det hurtigt for enhver graf, ville også løse tusindvis af andre problemer hurtigt og afgøre spørgsmålet P mod NP. Modsætningen til Euler-veje, som bruger hver kant én gang, er slående: Euler viste i 1736, at optælling af knudepunkterne af ulige grad afgør det spørgsmål med det samme. De bedste eksakte metoder til Hamilton-kredse tager stadig eksponentiel tid. Dynamisk programmering over alle delmængder af knudepunkter, fundet af Richard Bellman og af Michael Held og Richard Karp i 1962, kræver omkring n² × 2ⁿ skridt, og Andreas Björklunds randomiserede metode fra 2010 omkring 1,657ⁿ. I praksis klarer backtracking med god beskæring grafer med nogle få dusin knudepunkter, og handelsrejsendes problem, som søger den korteste Hamilton-kreds, er den vægtede udgave af det samme spørgsmål.
Gray-koder og hyperterningen
Skriv tallene 0 til 7 som 3-bit-koder og forbind to koder, når de adskiller sig i præcis én bit: resultatet er grafen for en terning. En Hamilton-kreds gennem den, for eksempel 000, 001, 011, 010, 110, 111, 101, 100, opregner alle otte koder, så hver adskiller sig fra den foregående i en enkelt bit. En sådan liste er en Gray-kode, opkaldt efter Frank Gray fra Bell Labs, som beskrev den i et patent indleveret i 1947. Enhver hyperterning har en: skriv koderne med én bit færre, derefter den samme liste baglæns, og sæt et 0 foran den første halvdel og et 1 foran den anden. Drejegivere bruger Gray-koder, så en aflæsning mellem to stillinger aldrig er mere end ét skridt forkert. Terningen har 6 Hamilton-kredse og 4-bit-hyperterningen 1.344.
Prøv det selv
Åbn Hamilton-vej-udforskeren for selv at prøve Hamiltons gåde, med stiplede ringe, der viser, hvor du kan gå hen, eller skift til Søgning og se backtracking arbejde: vejen vokser, røde streger markerer, hvor den vender om, og søjlerne tæller knuderne pr. vejlængde. Slå blindgyde-tjekket, sammenhængstjekket og Warnsdorffs rækkefølge til og fra, sammenlign hvor mange knuder hver kræver, tæl alle kredse i en lille graf, eller tegn din egen graf og se, hvilke af de hurtige tests der gælder.
Ofte stillede spørgsmål
Er en graf med et Euler-kredsløb også hamiltonsk, eller omvendt?
Ingen af delene følger af den anden. Butterflyen, to trekanter med et fælles knudepunkt, har et Euler-kredsløb, fordi hver grad er lige, men ingen Hamilton-kreds, da det fælles knudepunkt skulle passeres to gange. Den fuldstændige graf K₄ har Hamilton-kredse, men alle fire knudepunkter har grad 3, så den har intet Euler-kredsløb.
Kan en computer ikke bare prøve alle rækkefølger?
Kun ved små grafer. Der er n! rækkefølger af n knudepunkter, omkring 2,4 × 10¹⁸ for 20. Backtracking klarer det langt bedre, fordi den kun følger kanter og opgiver en delvej, så snart den går i stå: den finder alle 30 kredse i dodekaederet med 20 knudepunkter på omkring 1.400 skridt. Men for nogle grafer vokser antallet af delveje alligevel eksponentielt, og ingen metode kendes, der undgår dette for enhver graf.
Er Hamilton-vej-problemet lettere end kreds-problemet?
Nej, begge er NP-fuldstændige. Hvert kan omsættes til det andet: tilføj et nyt knudepunkt forbundet med hvert gammelt, og den gamle graf har en Hamilton-vej præcis når den nye har en Hamilton-kreds. Den anden vej bliver et kreds-problem til et vej-problem ved at tilføje en kopi af et knudepunkt, med de samme naboer, og et nyt endeknudepunkt hængt på knudepunktet og et andet på kopien.
Hvorfor skal en springerrundtur på et 5 × 5-bræt begynde på hjørnefarven?
Af de 25 felter har 13 hjørnernes farve og 12 den anden, og en springer skifter farve ved hvert træk. En rundtur over 25 felter skifter farverne, så den begynder og ender på den farve, der har flest felter. Appen finder alle 1.728 åbne rundture på 5 × 5-brættet, 864 hvis en rundtur og dens omvending tæller som én, og hver begynder og ender på et felt i hjørnefarven.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn Hamilton-vej-udforskeren