Hyperkubdiagram - Hypercube graph

Hyperkubgraf
Hyperkubgraf Q 4
Hörn	2 n
Kanter	2 n −1 n
Diameter	n
Omkrets	4 om n ≥ 2
Automorfismer	n ! 2 n
Kromatiskt tal	2
Spektrum	${\ displaystyle \ {(n-2k)^{\ binom {n} {k}}; k = 0, \ ldots, n \}}$
Egenskaper	Symmetrisk Avstånd regelbunden Unit avstånd Hamiltonian Tvådelad
Notation	Q n
Tabell över grafer och parametrar

I grafteori , den hyperkub graf Q _n är grafen bildas av hörnen och kanterna på en n dimensionell hyperkub . Till exempel är det kubiska diagrammet Q ₃ grafen som bildas av de 8 hörnen och 12 kanterna på en tredimensionell kub. Q _n har 2 ⁿ hörn , 2 ^{n −1} n kanter och är en vanlig graf med n kanter som rör varje toppunkt.

Hyperkubgrafen Q _n kan också konstrueras genom att skapa en toppunkt 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 toppunkt för varje n -siffrigt binärt tal , med två hörn intill när deras binära representationer skiljer sig åt i en enda siffra. Det är den n -faldiga kartesiska produkten av den fullständiga grafen med två hörn och kan brytas ned i två kopior av Q _{n -1 som är} anslutna till varandra genom en perfekt matchning .

Hyperkubdiagram bör inte förväxlas med kubikgrafer , som är grafer som har exakt tre kanter som rör varje toppunkt. Det enda hyperkubdiagrammet Q _n som är ett kubikdiagram är det kubikdiagrammet Q ₃ .

Konstruktion

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

Den hyperkub graf Q _n kan konstrueras från familjen av delmängder av en uppsättning med n element, genom att göra ett vertex för varje möjlig delmängd och förenande två hörn av en kant när de motsvarande undergrupper skiljer sig åt i ett enda element. På motsvarande sätt kan den konstrueras med hjälp av 2 ⁿ hörn märkta med n -bit binära tal och ansluta två hörn med en kant när Hamming -avståndet för deras etiketter är en. Dessa två konstruktioner är nära besläktade: ett binärt tal kan tolkas som en uppsättning (uppsättningen positioner där det har en 1 -siffra), och två sådana uppsättningar skiljer sig åt i ett enda element när motsvarande två binära tal har Hammingavstånd ett.

Alternativt kan Q _n konstrueras från den sammanfogade föreningen mellan två hyperkubar Q _{n - 1} genom att lägga till en kant från varje hörn i en kopia av Q _{n - 1} till motsvarande toppunkt i den andra kopian, såsom visas i figuren. Fogkanterna bildar en perfekt matchning .

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

Exempel

Diagrammet Q ₀ består av en enda toppunkt, medan Q ₁ är den fullständiga grafen på två hörn och Q ₂ är en cykel med längd  4 .

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

Diagrammet Q ₄ är Levi -grafen för Möbius -konfigurationen . Det är också riddarens graf för ett toroidalt schackbräde . ${\ displaystyle 4 \ times 4}$

Egenskaper

Bipartiteness

Varje hyperkubgraf är bipartit : den kan färgas med bara två färger. De två färgerna i denna färgning kan hittas från delmängden konstruktion av hyperkubdiagram, 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 tesseract 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 toppunkt exakt en gång. Dessutom finns det en Hamiltonisk väg mellan två hörn u och v om och bara 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 på hyperkubens dimension och konstruktionen av hyperkubgrafen genom att förena två mindre hyperkubar med en matchning.

Hyperkubens Hamiltonicitet har ett nära samband med teorin om gråkoder . Mer exakt finns det en bijektiv korrespondens mellan uppsättningen n -bit cykliska gråkoder och uppsättningen Hamiltonian cykler i hyperkuben Q _n . En analog egenskap gäller för acykliska n -bitars gråkoder och hamiltonsvägar.

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

Övriga fastigheter

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

• är Hasse -diagrammet över en ändlig boolsk algebra .
• är en median graf . Varje mediangraf är en isometrisk subgraf av en hyperkub och kan formas som en indragning 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 signerade 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 hyperkubediagrammet från delmängder av en uppsättning n element, välja en distinkt enhetsvektor för varje uppsättningselement och placera hörnet som motsvarar uppsättningen S vid summan av vektorerna i S .
• är en n -vertex -ansluten 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äkt ( n - 4) 2 ^{n - 3} + 1 .
• har exakt spännande träd .${\ displaystyle 2^{2^{n} -n-1} \ prod _ {k = 2}^{n} k^{n \ välj k}}$
• har bandbredd exakt .${\ displaystyle \ sum _ {i = 0}^{n-1} {\ binom {i} {\ lfloor i/2 \ rfloor}}}$
• har achromatiskt tal proportionellt mot , men proportionalitetskonstanten är inte exakt känd.${\ displaystyle {\ sqrt {n2^{n}}}}$
• har som egenvärden för dess adjacensmatris siffrorna ( - n , - n + 2, - n + 4, ..., n - 4, n - 2, n ) och som egenvärdena för dess Laplacian -matris siffrorna (0 , 2, ..., 2 n ) . Den k : te egenvärdet har mångfald i båda fallen.${\ displaystyle {\ binom {n} {k}}}$
• har isoperimetriskt tal h ( G ) = 1 .

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

Problem

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

Problemet med att hitta den längsta vägen eller cykeln som är en inducerad delgraf av ett givet hyperkubdiagram är känt som orm-i-lådan- problemet.

Szymanskis gissning rör lämpligheten av en hyperkub som nätverkstopologi för kommunikation. Den säger att oavsett hur man väljer en permutation som förbinder varje hyperkubspik till en annan topppunkt som den ska vara ansluten till, finns det alltid ett sätt att ansluta dessa par hörn genom vägar som inte delar någon riktad kant.

Se även

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

Anteckningar

Referenser

• Harary, F .; Hayes, JP; Wu, H.-J. (1988), "En undersökning av teorin om hyperkubgrafer", Computers & Mathematics with Applications , 15 (4): 277–289, doi : 10.1016/0898-1221 (88) 90213-1 , hdl : 2027.42/27522.