Halverad kubgraf

Halverad kubgraf
Den halverade kubgrafen 1 / 2 Q 3
Vertices	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	1/2 _ _ Q n
Tabell över grafer och parametrar

Konstruktion av två demikuber (vanliga tetraedrar, bildar en stella octangula ) från en enda kub. Den halverade kubgrafen av dimension tre är grafen över hörn och kanter på en enda demikub. Den halverade kubgrafen av dimension fyra inkluderar alla kubens hörn och kanter, och alla kanter på de två demikuberna.

I grafteorin är den halverade kubgrafen eller halvkubgrafen av dimensionen n grafen för demihyperkuben , bildad genom att koppla ihop par av hörn på avstånd exakt två från varandra i hyperkubgrafen . Det vill säga att det är hyperkubens halva kvadrat . Detta anslutningsmönster producerar två isomorfa grafer , bortkopplade från varandra, som var och en är den halverade kubgrafen.

Motsvarande konstruktioner

Konstruktionen av den halverade kubgrafen kan omformuleras i termer av binära tal . Topppunkterna i en hyperkub kan märkas med binära tal på ett sådant sätt att två hörn ligger intill exakt när de skiljer sig åt i en enda bit. Demikuben kan vara konstruerad från hyperkuben som det konvexa skrovet av delmängden av binära tal med ett jämnt antal bitar som inte är noll (de onda talen ), och dess kanter förbinder par av tal vars Hamming-avstånd är exakt två.

Det är också möjligt att konstruera den halverade kubgrafen från en lågdimensionell hyperkubgraf, utan att ta en delmängd av hörnen:

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

där den upphöjda skriften 2 betecknar kvadraten på hyperkubgrafen Q _{n − 1} , den graf som bildas genom att koppla ihop par av hörn vars avstånd är högst två i den ursprungliga grafen. Till exempel kan den halverade kubgrafen av dimension fyra formas av en vanlig tredimensionell kub genom att behålla kubkanterna och lägga till kanter som förbinder par av hörn som är på motsatta hörn av samma kvadratiska yta.

Exempel

Den halverade kubgrafen ${\tfrac {1}{2}}Q_{3}$ av dimension 3 är den fullständiga grafen K ₄ , grafen för tetraedern . Den halverade kubgrafen ${\tfrac {1}{2}}Q_{4}$ av dimension 4 är K _2,2,2,2 , grafen för den fyrdimensionella reguljära polytopen , den 16-celler . Den halverade kubgrafen ${\tfrac {1}{2}}Q_{5}$ av dimension fem kallas ibland Clebsch-grafen och är komplementet till den vikta kubgrafen för dimension fem, som är den som oftast kallas Clebsch-grafen. Det finns i den 5-dimensionella enhetliga 5-polytopen , 5-demikuben .

Egenskaper

Eftersom det är den tvådelade halvan av en avståndsregelbunden graf , är den halverade kubgrafen i sig avståndsregelbunden. Och eftersom den innehåller en hyperkub som en spännande subgraf , ärver den från hyperkuben alla monotona grafegenskaper, till exempel egenskapen att innehålla en Hamiltonsk cykel .

Som med hyperkubgraferna, och deras isometriska (avståndsbevarande) subgrafer till de partiella kuberna , kan en halverad kubgraf bäddas in isometriskt i ett verkligt vektorrum med Manhattan-metriken ( L ₁ avståndsfunktion). Detsamma gäller för de isometriska subgraferna av halverade kubgrafer, som kan kännas igen i polynomtid ; detta bildar en nyckelsubrutin för en algoritm som testar om en given graf kan vara inbäddad isometriskt i en Manhattan-metrik.

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

Sekvens

De två graferna som visas är symmetriska D _n och B _n Petrie polygonprojektioner (2( n − 1) och n dihedrisk symmetri ) av den relaterade polytopen som kan inkludera överlappande kanter och hörn.

n	Polytop	Graf	Vertices	Kanter
2	Linjesegmentet		2	–
3	tetraeder		4	6
4	16-celler		8	24
5	5-demikub		16	80
6	6-demikub		32	240
7	7-demikub		64	672
8	8-demikub		128	1792
9	9-demikub		256	4608
10	10-demikub		512	11520

externa länkar

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