Halverad kubgraf - Halved cube graph

Halverad kubgraf
Den halverade kubgrafen ${\ displaystyle {\ tfrac {1} {2}} Q_ {3}}$
Hörn	2 n-1
Kanter	n ( n-1 ) 2 n -3
Automorfismer	n ! 2 n-1 , för n > 4 n ! 2 n , för n = 4 (2 n -1 ) !, för n <4
Egenskaper	Symmetriskt avstånd regelbundet
Notation	${\ displaystyle {\ tfrac {1} {2}} Q_ {n}}$
Tabell över diagram och parametrar

Konstruktion av två demikuber (vanlig tetraeder, bildande en stella octangula ) från en enda kub. Den halverade kubdiagrammet för dimension tre är grafen för hörn och kanter på en enda demikub. Den halverade kubdiagrammet för dimension fyra inkluderar alla kubhörnor och kanter och alla kanterna på de två demikuberna.

I grafteorin är den halverade kubgrafen eller halva kubgrafen för dimension n grafen för demihyperkuben , bildad genom att ansluta par av hörn på avstånd exakt två från varandra i hyperkubdiagrammet . Det vill säga, det är halvkvadrat i hyperkuben. Detta anslutningsmönster ger två isomorfa grafer, kopplade från varandra, var och en är den halverade kubgrafen.

Motsvarande konstruktioner

Konstruktionen av den halverade kubgrafen kan omformuleras i termer av binära tal . Hörnpunkterna i en hyperkub kan märkas av binära tal på ett sådant sätt att två hörn är intill varandra när de skiljer sig åt i en enda bit. Demikuben kan konstrueras från hyperkuben som det konvexa skrovet för delmängden av binära tal med ett jämnt antal icke-nollbitar (de onda siffrorna ) och dess kanter förbinder talpar vars Hamming-avstånd är exakt två.

Det är också möjligt att konstruera den halverade kubgrafen från en nedre dimensionell hyperkubgraf utan att ta en delmängd av topparna:

${\ displaystyle {\ frac {1} {2}} Q_ {n} = Q_ {n-1} ^ {2}}$

där exponenten 2 betecknar den kvadrat av hyperkub grafen Q _{n  - 1} , diagrammet som bildas genom att ansluta par av hörn, vilkas avstånd är som mest två i den ursprungliga grafen. Till exempel kan den halverade kubdiagrammet för dimension fyra bildas av en vanlig tredimensionell kub genom att hålla kubkanterna och lägga till kanter som förbinder par av hörn som ligger i motsatta hörn av samma kvadratiska yta.

Exempel

Det halverade kubdiagrammet för dimension 3 är det kompletta diagrammet K ₄ , tetraederns graf . Den halverade kubgrafen för dimension 4 är K _2,2,2,2 , grafen för den fyrdimensionella vanliga polytopen , 16-cellen . Den halverade kubgrafen för dimension fem är ibland känd som Clebsch-grafen och är komplementet till den vikta kubgrafen för dimension fem, vilket är den som vanligtvis kallas Clebsch-grafen. Den finns i den 5-dimensionella enhetliga 5-polytopen , 5-demikuben . ${\ displaystyle {\ tfrac {1} {2}} Q_ {3}}$ ${\ displaystyle {\ tfrac {1} {2}} Q_ {4}}$${\ displaystyle {\ tfrac {1} {2}} Q_ {5}}$

Egenskaper

Eftersom det är bipartithalvan av en distansregelbunden graf är den halverade kubgrafen själv distansregelbunden. Och eftersom den innehåller en hyperkub som en spännande undergraf , ärver den från hyperkuben alla monotiska grafegenskaper, till exempel egenskapen att innehålla en Hamilton-cykel .

Precis som med hyperkubdiagrammen och deras isometriska (avståndsbevarande) underbilder de partiella kuberna , kan en halverad kubdiagram inbäddas isometriskt i ett verkligt vektorutrymme med Manhattan-metriska ( L ₁ avståndsfunktion). Detsamma gäller för de isometriska delbilderna av halverade kubdiagram, som kan kännas igen på polynomtid ; detta bildar en nyckelundervisning för en algoritm som testar om en given graf kan inbäddas isometriskt i ett Manhattan-mått.

För varje halverad kubgraf med dimension fem eller mer är det möjligt att (felaktigt) färga topparna med två färger, på ett sådant sätt att den resulterande färgade grafen inte har några icke-privata symmetrier. För graferna för dimension tre och fyra behövs fyra färger för att eliminera alla symmetrier.

Sekvens

De två diagrammen som visas är symmetriska D _n och B _n Petrie polygon utsprång (2 ( n  - 1) och n tvåplansvinkel symmetri ) av den relaterade polytope som kan innefatta överlappande kanter och hörn.

n	Polytope	Graf	Hörn	Kanter
2	Linjesegmentet		2	-
3	tetraeder		4	6
4	16-cell		8	24
5	5-demicube		16	80
6	6-demicube		32	240
7	7-demicube		64	672
8	8-demicube		128	1792
9	9-demicube		256	4608
10	10-demicube		512	11520

Referenser

externa länkar

• Weisstein, Eric W. "Halved Cube Graph" . MathWorld .