Hypercube graf

Hyperkubgraf
Hyperkubgrafen Q 4
Vertices	2 n
Kanter	2 n – 1 n
Diameter	n
Omkrets	4 om n ≥ 2
Automorfismer	n ! 2 n
Kromatiskt nummer	2
Spektrum	$\{(n-2k)^{\binom {n}{k}};k=0,\ldots ,n\}$
Egenskaper	Symmetriskt avstånd regelbundet Enhetsavstånd Hamiltonian Bipartite
Notation	Q n
Tabell över grafer och parametrar

I grafteorin är hyperkubgrafen Qn den graf _som bildas av hörn och kanter på en n - dimensionell hyperkub . Till exempel kubgrafen Q ₃ den graf som bildas av de 8 hörnen och 12 kanterna på en tredimensionell kub. Qn _n har 2 ⁿ hörn , 2 ^{n – 1} kanter , och är en vanlig graf med n kanter som rör vid varje vertex.

Hyperkubgrafen Qn _n kan också konstrueras genom att skapa en vertex för varje delmängd av en n -elementuppsättning, med två hörn intill när deras delmängder skiljer sig åt i ett enda element, eller genom att skapa en vertex för varje - siffrigt binärt tal , med två hörn intill när deras binära representationer skiljer sig i en enda siffra. Det är den n -faldiga kartesiska produkten av den kompletta grafen med två vertex och kan delas upp i två kopior av Q _{n – 1} kopplade till varandra genom en perfekt matchning .

Hyperkubgrafer ska inte förväxlas med kubiska grafer , som är grafer som har exakt tre kanter som rör varje vertex. Den enda hyperkubgrafen Q ₃ som är en kubisk graf är den kubiska grafen Q ₃ .

Konstruktion

Konstruktion av Q ₃ genom att koppla ihop par av motsvarande hörn i två kopior av Q ₂

Hyperkubgrafen Qn _. kan konstrueras från familjen av delmängder av en mängd med n element, genom att göra en vertex för varje möjlig delmängd och sammanfoga två hörn med en kant närhelst motsvarande delmängder skiljer sig åt i ett enda element På motsvarande sätt kan den konstrueras med 2 ⁿ hörn märkta med n -bitars binära tal och förbinda två hörn med en kant närhelst Hamming-avståndet för deras etiketter är ett. Dessa två konstruktioner är nära besläktade: ett binärt tal kan tolkas som en uppsättning (uppsättningen positioner där den har en siffra ), och två sådana uppsättningar skiljer sig åt i ett enda element när de motsvarande två binära talen har Hamming-avstånd ett.

Alternativt kan Q _n konstrueras från den disjunkta föreningen av två hyperkuber _{Qn 1} − , genom att lägga till en kant från varje vertex i en kopia av Q _{n − 1} till motsvarande vertex i den andra kopian, som visas i figuren. Skarvkanterna bildar en perfekt matchning .

En annan konstruktion av Q _n är den kartesiska produkten av n kompletta grafer med två vertex K ₂ . Mer allmänt kallas den kartesiska produkten av kopior av en komplett graf en Hamming-graf ; hyperkubgraferna är exempel på Hamming-grafer.

Exempel

Grafen Q ₀ består av en enda vertex, medan Q ₁ är den kompletta grafen på två hörn.

Q ₂ är en cykel av längd 4 .

Grafen Q ₃ är 1-skelettet i en kub och är en plan graf med åtta hörn och tolv kanter .

Grafen Q ₄ är Levi-grafen för Möbius-konfigurationen . Det är också riddarens graf för ett toroidformat $4\times 4$ schackbräde .

Egenskaper

Bipartihet

Varje hyperkubgraf är tvådelad : den kan färgas med endast två färger. De två färgerna i denna färgning kan hittas från delmängdskonstruktionen av hyperkubgrafer, genom att ge en färg till delmängderna som har ett jämnt antal element och den andra färgen till delmängderna med ett udda antal element.

Hamiltonicitet

En Hamiltonsk cykel på en tesserakt med hörn märkta med en 4-bitars cyklisk grå kod

Varje hyperkub Q _n med n > 1 har en Hamiltonsk cykel , en cykel som besöker varje vertex exakt en gång. Dessutom existerar en Hamiltonsk bana mellan två hörn u och v om och endast om de har olika färger i en 2 -färgning av grafen. Båda fakta är lätta att bevisa med hjälp av induktionsprincipen om hyperkubens dimension, och konstruktionen av hyperkubgrafen genom att sammanfoga två mindre hyperkuber med en matchning.

Hyperkubens Hamiltonicitet är nära relaterad till teorin om gråkoder . Närmare bestämt finns det en bijektiv överensstämmelse mellan mängden n -bitars cykliska Gray-koder och mängden Hamiltons cykler i hyperkuben Qn _. En analog egenskap gäller för acykliska n -bitars gråkoder och Hamiltonska banor.

Ett mindre känt faktum är att varje perfekt matchning i hyperkuben sträcker sig till en Hamiltonsk cykel. Frågan om varje matchning sträcker sig till en Hamilton-cykel är fortfarande ett öppet problem.

Övriga fastigheter

Hyperkubgrafen Q _n (för n > 1 ):

• är Hasse-diagrammet för en finit boolesk algebra .
• är en mediangraf . Varje mediangraf är en isometrisk subgraf av en hyperkub och kan bildas som en retraktion av en hyperkub.
• har mer än 2 ^{2 n-2} perfekta matchningar. (detta är en annan konsekvens som lätt följer av den induktiva konstruktionen.)
• är bågtransitiv och symmetrisk . Symmetrierna för hyperkubgrafer kan representeras som teckenförsedda permutationer .
• innehåller alla cykler med längden 4, 6, ..., 2 ⁿ och är således en bipancyklisk graf .
• kan ritas som en enhetsavståndsgraf i det euklidiska planet genom att använda konstruktionen av hyperkubgrafen från delmängder av en uppsättning av n element, välja en distinkt enhetsvektor för varje uppsättningselement och placera vertexen som motsvarar mängden S vid summan av vektorerna i S .
• är en n -vertex-kopplad graf , enligt Balinskis sats
• är plan (kan ritas utan korsningar) om och endast om n ≤ 3 . För större värden på n har hyperkuben släktet ( n − 4)2 ^{n − 3} + 1 .
• har exakt $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{ n \choose k}$ spännande träd .
• har bandbredd exakt $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ .
• har ett akromatiskt tal proportionellt mot ${\sqrt {n2^{n}}}$ , men proportionalitetskonstanten är inte känd exakt.
• har som egenvärden för sin närliggande matris talen (− n , − n + 2, − n + 4, ... , n − 4, n − 2, n ) och som egenvärden för dess Laplacian matris talen (0 , 2, ..., 2 n ) . Det k: te egenvärdet har multiplicitet ${\binom {n}{k}}$ i båda fallen.
• har isoperimetriskt tal h ( G ) = 1 .

Familjen Q _n för alla n > 1 är en Lévy-familj av grafer

Problem

Maximala längder på ormar ( L _s ) och spolar ( L _c ) i problemet med ormar-i-lådan för dimensioner n från 1 till 4

Problemet med att hitta den längsta vägen eller cykeln som är en inducerad subgraf av en given hyperkubgraf kallas orm-i-lådan- problemet.

Szymanskis gissning rör lämpligheten av en hyperkub som nätverkstopologi för kommunikation. Det sägs att oavsett hur man väljer en permutation som förbinder varje hyperkub-vertex med en annan vertex som den ska kopplas till, så finns det alltid ett sätt att koppla ihop dessa par av hörn med vägar som inte delar någon riktad kant.

Se även

• de Bruijn graf
• Kubanslutna cykler
• Fibonacci kub
• Vikt kubdiagram
• Frankl–Rödl graf
• Halverad kubgraf
• Hypercube internetwork topologi
• Delvis kub

Anteckningar

• Harary, F. ; Hayes, JP; Wu, H.-J. (1988), "A survey of the theory of hypercube graphs", Computers & Mathematics with Applications , 15 (4): 277–289, doi : 10.1016/0898-1221(88)90213-1 , hdl : 2027.42/ .