Vej
Undersøgte knuder
Hamilton-kreds
Hamilton-vej

Tilstand

    Mål

    Mere om Hamilton-veje og Hamilton-kredse

    Hamilton-vej-udforsker

    I 1857 opfandt William Rowan Hamilton en gåde: gå langs kanterne på et dodekaeder, så du passerer hvert af dets 20 hjørner præcis én gang og ender, hvor du begyndte. En sådan rute kaldes i dag en Hamilton-kreds. Den er let at tjekke og i almindelighed svær at finde. Tegn selv en på Hamiltons dodekaeder, på et skakbræt eller på en graf, du tegner, eller se en backtracking-søgning jage efter en, tæl de blindgyder, den havner i, og se, hvor meget nogle få enkle tjek forkorter søgningen. Vælg en graf og et mål: en kreds, der vender tilbage til sit udgangspunkt, eller en vej. Tegn: klik på et knudepunkt for at begynde og derefter på en nabo ad gangen; stiplede ringe viser, hvor du kan gå hen. Et klik på det sidste knudepunkt, Tilbage eller Fortryd går et skridt tilbage, og Tip nævner et næste skridt, der stadig kan fuldføres. Søgning: med Kør eller Skridt løber en backtracking-søgning, som føjer knudepunkter til, indtil den går i stå, og så vender tilbage; røde streger viser tilbageskridtene, og søjlerne tæller knuderne pr. vejlængde. Før den starter, vælger et klik på et knudepunkt, hvor den begynder. Afkrydsningsfelterne slår beskæringen til og fra, Sammenlign kører den samme søgning med og uden, og Tæl alle tæller hver kreds eller vej i en lille graf. Rediger: klik for at tilføje et knudepunkt, klik på to knudepunkter for at forbinde eller adskille dem, træk for at flytte et, og Slet fjerner det valgte knudepunkt.

    Sådan virker det

    1. Vælg en graf, for eksempel Hamiltons dodekaeder, Petersen-grafen eller en springerrundtur, eller tegn din egen under Rediger, og vælg en kreds eller en vej som mål.
    2. Klik under Tegn på et knudepunkt for at begynde og derefter på den ene nabo efter den anden. Tilbage og Fortryd går et skridt tilbage, og Tip viser et næste skridt, der stadig kan fuldføres.
    3. Tryk under Søgning på Kør eller Skridt for at se backtracking lede efter en rute, slå beskæringen til og fra, og tryk på Sammenlign for at se, hvor mange knuder hver udgave kræver.

    Hamilton over for Euler

    En Euler-vej bruger hver kant én gang; en Hamilton-vej besøger hvert knudepunkt én gang. Det lyder ens, men opfører sig meget forskelligt. Om en sammenhængende graf har en Euler-vej, afgøres ved at tælle knudepunkterne af ulige grad, som Euler viste i 1736: den har en, når der ingen er, eller der er to. For Hamilton-veje kendes ingen sådan regel. At afgøre, om en graf har en Hamilton-kreds, er NP-fuldstændigt, et af de 21 problemer på Richard Karps liste fra 1972, så en hurtig metode til det ville give hurtige metoder til tusindvis af andre svære problemer. Det, der findes, er betingelser, som afgør nogle grafer. Diracs sætning fra 1952 sikrer en Hamilton-kreds, når hvert knudepunkt har grad mindst n/2, og Ores fra 1960, når to knudepunkter, der ikke er forbundet, altid har grader med sum mindst n; et knudepunkt af grad 1, et skæreknudepunkt eller to farveklasser af forskellig størrelse udelukker en.

    Sådan arbejder søgningen

    Backtracking bygger vejen op et knudepunkt ad gangen og tager, når den går i stå, det sidste skridt tilbage og prøver den næste nabo. Den finder altid en Hamilton-kreds, hvis der er en, men antallet af delveje kan vokse eksponentielt. På 5 × 5-gitteret, som ingen Hamilton-kreds har, undersøger almindelig backtracking 153.745 knuder, før den er sikker. To tjek standser håbløse veje tidligt: et ubesøgt knudepunkt med færre end to ledige naboer kan ikke længere passes ind i en kreds, og når de ubesøgte knudepunkter falder fra hinanden i adskilte dele, kan ingen enkelt vej dække dem. Med begge tager det samme bevis 1.761 knuder. Warnsdorffs regel fra 1823, som først prøver naboen med færrest videre træk, finder en springerrundtur på 8 × 8 fra et hjørne på 64 træk uden en eneste blindgyde.

    Ofte stillede spørgsmål

    Hvad er forskellen på en Hamilton-vej og en Hamilton-kreds?

    En Hamilton-vej besøger hvert knudepunkt i en graf præcis én gang. En Hamilton-kreds gør det samme og vender så via én kant mere tilbage til udgangspunktet, så den kan begynde ved hvilket som helst af sine knudepunkter. Enhver graf med en Hamilton-kreds har en Hamilton-vej (udelad én kant af kredsen), men ikke omvendt: Petersen-grafen har Hamilton-veje og ingen Hamilton-kreds.

    Har dodekaederet en Hamilton-kreds?

    Ja, 30 af dem, når hver kreds tælles én gang uanset udgangspunkt og retning. Hamilton gjorde det i 1857 til det ikosiske spil, en plade med de 20 hjørner af et fladtrykt dodekaeder mærket med konsonanter, og solgte rettighederne for 25 pund til den londonske legetøjsfabrikant John Jaques and Son. Tæl alle finder de 30 kredse på omkring 1.400 knuder.

    Hvorfor har et 5 × 5-gitter ingen Hamilton-kreds?

    Farv de 25 punkter som et skakbræt: 13 får den ene farve og 12 den anden, og hvert skridt går til den anden farve. En kreds skifter farve hele vejen rundt, så den kræver lige mange af hver, hvilket 13 og 12 ikke giver. Det samme argument gælder for ethvert gitter med et ulige antal punkter, for en springer på et 5 × 5- eller 7 × 7-bræt (en springer skifter altid feltfarve) og for Herschel-grafen, hvis to klasser har 6 og 5 knudepunkter. En Hamilton-vej er stadig mulig: den begynder og ender på den største farve.

    Hvordan finder Warnsdorffs regel en springerrundtur?

    H. C. von Warnsdorff foreslog i 1823 altid at flytte springeren til det felt, hvorfra den har færrest videre træk. Felter nær kanter og hjørner, som let bliver skåret fra, besøges dermed tidligt, mens springeren endnu kan komme til dem. Reglen er en tommelfingerregel, ikke en garanti, og lige tilfælde må brydes på en eller anden måde, men på et 8 × 8-bræt fuldfører den som regel en rundtur uden at gå tilbage. Sammen med backtracking, som i denne app, finder den åbne rundture fra 5 × 5 og opefter og lukkede rundture på 6 × 6- og 8 × 8-brættet.

    Hvor mange Hamilton-kredse har en fuldstændig graf?

    (n − 1)!/2 for n ≥ 3. Hold udgangsknudepunktet fast; de øvrige n − 1 kan følge i vilkårlig rækkefølge, og hver kreds tælles to gange, én gang per retning. K₆ har 5!/2 = 60 og K₁₀ har 181.440. Det er de rundture, en handelsrejsende skal vælge imellem, og derfor holder det så hurtigt op med at være muligt at prøve dem alle.

    Er du klar til at prøve?

    Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

    Gå til Editor