Hamiltonske sykluser i en n-kube

[Charlatan]

http://no.wikipedia.org/wiki/Grafteori

I grafteori kan vi definere en hamiltonsk syklus som slik:

En graf har en hamiltonsk syklus hvis og bare hvis det finnes en vei som går innom hvert hjørne bare én gang.

F.eks har enhver komplette graf (en graf hvor hvert hjørne er koblet med alle andre) en hamiltonsk syklus, fordi vi kan markere tilfeldig hjørnene [tex]v_1, v_2, ..., v_n[/tex] og la veien være [tex]v_1 \to v_2 ... \to v_n[/tex].


En n-kube er grafen du får hvor hjørnene i den n-dimensjonale kuben er hjørner i grafen, og kantene er kanter i grafen. En 2-kube (kvadrat) dannes ved å starte med en 1-kube (altså et linjestykke hvor endene er hjørner i grafen, og linjestykket selv er en kant), og deretter koble hvert hjørne i denne til et tilsvarende hjørne i en annen 1-kube. En 3-kube dannes på samme måte ved å bruke to 2-kuber. Slik kan man fortsette til man får en n-kube.

Oppgaven:

Vis at enhver n-kube har en hamiltonsk syklus, for n > 0.

[daofeishi]

Jeg tror en "Hamiltonian cycle" kalles en "Hamiltonsk løkke" på norsk, Jarle

[Charlatan]

takk, da vet jeg det! men det forandrer ikke oppgaven

[daofeishi]

Nei, det gjør det ikke. Jeg er på vei til middag, men jeg kan vel prøve meg på et "handwaving proof."

Koordinatene for hjørnene til en enhets-n-kube er gitt ved n-tuplene i {0,1}[sup]n[/sup].

Det finnes en (triviell) bijeksjon mellom disse n-tuplene og alle tall i binærsystemet mellom 0 og 2[sup]n+1[/sup]-1.

To noder i n-kube-grafen deler en kant hvis og bare hvis differansen mellom de korresponderende binærtallene er en potens av 2. (*Vifte vilt med hånda*)

Kan vi finne en rekke som beskriver alle elementene i [0,1][sup]n[/sup]. der differansen mellom etterfølgende elementer er en potens av 2? Jada.
a[sub]1[/sub] = 0, a[sub]n+1[/sub] = a[sub]n[/sub]+1


Godt mulig det skjuler seg en feil her, men gjør det ikke det så kan det formaliseres.

Det som må vises er nå er hvorfor det stemmer at differansen mellom binærtallene må være en potens av 2. Dette kan gjøres induktivt. En merking for et vanlig kvadrat ville være

Kode: Velg alt

(0,1)  ----- (1,1)
  |            |
  |            |
  |            |
(0,0)  ----- (1,0) 

Og lemmaet følger via ekstensjon fra en n-kubegraf til neste (n+1)-kubegraf.

[Charlatan]

Faktisk så nevnte oppgaveteksten dette:

"Det er en graf med 2^n hjørner merket med de n-sifrede binærtallene, hvor to hjørner er koblet hvis binærtallene er like utenom nøyaktig ett siffer."

Ekstra cred for å finne dette ut uavhengig av det!

Jeg løste den imidlertidig uten å ta hensyn til dette, fordi jeg tok et helt annet utgangspunkt.

Jeg forstår ikke helt hva du mener med "rekken som beskriver alle elementene i [0,1]^n". Hvordan kan en rekke beskrive en n-tuppel? Og hvordan er [0,1]^n notasjonen definert?

[daofeishi]

Sorry for skrivefeil med klammeparanteser{0,1}[sup]n[/sup] er definert som det kartesiske produktet av settet med seg selv n ganger, altså alle n-tupler hvor elementene er 0 eller 1. Det er slik jeg automatisk tenker på hjørnene i en n-kube, så det var et naturlig utgangspunkt for meg. Jeg er litt uklar over, jeg skifter lettfeldig mellom representasjon som n-tuppel og binærtall. En rekke med tall kan fint beskrive en rekke med n-tupler, hvis det eksisterer en bijeksjon mellom tallene og n-tuplene, som er det jeg benytter meg av. Det er kanskje lettere å ikke gå omveien med n-tupler.

Du kan gjerne få komme med din løsning og. Benytter du kanskje at enhver n-kubegraf består av sammenkoblede (n-1)-kubegrafer?

[Charlatan]

jeg følger deg nå!

okey, min løsning:

Vi går induktivt til verks:

For en 1-kube er den hamiltonske løkka åpenbart tilstede.

Anta nå at en r-kube er inneholder en hamiltonsk løkke. Merk hjørnene [tex](v_i)^n[/tex] slik at [tex]v_1 \to v_2 \to ... \to v_n [/tex] er en hamiltonsk løkke.

Vi danner nå en (r+1)-kube ved å koble to slike grafer. La en annen identisk graf ha løkken [tex]h_1 \to h_2 \to ... \to h_n[/tex] hvor [tex]h_i[/tex] tilsvarer [tex]v_i[/tex].

Når vi nå kobler dem sammen har vi at [tex]v_i[/tex] er koblet til [tex]h_i[/tex]. Derfor finnes det i (r+1)-kuben en løkke [tex]v_1 \to h_1 \to h_2 \to v_2 \to v_3 \to ... \to v_{n-1} \to v_n \to h_n[/tex]

Da har vi at hvis en r-kube har en hamiltonsk løkke, så har en r+1-kube det og. Og siden en 1-kube har en hamiltonsk løkke, har en n-kube det.

Forresten, det er slik at [tex]\{ 0,1 \} ^n \not = \{ 0,1 \} \times \{ 0,1 \} ^{n-1}[/tex] ?

[daofeishi]

Jepp, akkurat! Løkkene våres er også ganskje forskjellig. Hvis løkkene våre definerte n-dimensjonale skiløyper, ville jeg markert din med svart flagg

Og dette med notasjonen over... Du har muligens rett i det ja, siden høyresiden etter vanlige regler er et ordnet par - hvis ikke konvensjon/definisjon dikterer at de skal være like. Det finnes jo tross alt en enkel bijeksjon mellom begge sider. Det betyr igjen at jeg muligens var upresis når jeg sa "kartesisk produkt med seg selv n ganger", og burde kanskje heller sagt "n-tupler med elementer i det gitte settet," men nå overlater jeg spørsmålet til noen som er mer velskodd i mengdelære.

[mrcreosote]

Det naturlige oppfølgerspørsmålet: Hvor mange forskjellige hamiltonske sykler har en n-kube?

[mrcreosote]

Det naturlige oppfølgerspørsmålet: Hvor mange forskjellige hamiltonske sykler har en n-kube?

Det spørsmålet er nok rimelig vrient. Men å finne antall veier gjennom 1-, 2- og 3-kuben er ei fin telleoppgave.

[Charlatan]

Det er ihvertfall 2n. Faktisk så er det ei syklisk hamiltonsk løkke (slutter i et hjørne insident til hjørnet vi startet i) i alle n-kuber (som lett kan bevises med induksjon ved en liten forandring i induksjonsbeviset jeg skrev). Vi har da de hamiltonske løkkene [tex]v_i \to v_{i+1} \to ... \to v_n \to v_1 \to ... \to v_{i-1}[/tex] for alle [tex]1 \leq i \leq n[/tex] Dessuten er de motsatte veiene også hamiltonske løkker. Det gir 2n løkker.

Dette viser seg å være en dårlig nedre grense, men gir kanskje litt innsikt. Kan se litt mer på det.

Tror det er [tex]n \cdot 2^n[/tex] men har ikke bevis enda.

EDIT: er nok enda mer enn det..