Wykres sześcienny o połowę - Halved cube graph

Wykres sześcienny o połowę
Wykres sześcienny o połowę ${\displaystyle {\tfrac {1}{2}}Q_{3}}$
Wierzchołki	2 n-1
Krawędzie	n ( n- 1)2 n -3
Automorfizmy	n ! 2 n-1 , dla n > 4 n ! 2 n , dla n =4 (2 n -1 )!, dla n <4
Nieruchomości	Odległość symetryczna regularna
Notacja	${\displaystyle {\tfrac {1}{2}}Q_{n}}$
Tabela wykresów i parametrów

Konstrukcja dwóch półkostek (czworościanów regularnych, tworzących stella octgula ) z jednego sześcianu. Wykres sześcienny o połowie wymiaru trzeciego jest wykresem wierzchołków i krawędzi pojedynczego demisześcianu. Wykres sześcienny o połowie wymiaru czwartego zawiera wszystkie wierzchołki i krawędzie sześcianu oraz wszystkie krawędzie dwóch demikubów.

W teorii wykres The ow wykres kostki lub pół wykres kostki o wymiarze n jest wykresem demihypercube , utworzony przez połączenie ze sobą par wierzchołków na odległość dokładnie dwa ze sobą na wykresie hipersześcianu . Oznacza to, że jest pół-kwadrat z hipersześcianu. Ten wzorzec łączności tworzy dwa grafy izomorficzne, oddzielone od siebie, z których każdy jest podzielonym na pół grafem sześciennym.

Konstrukcje równoważne

Konstrukcję wykresu sześciennego o połowę można przeformułować za pomocą liczb binarnych . Wierzchołki hipersześcianu mogą być oznaczone liczbami binarnymi w taki sposób, że dwa wierzchołki sąsiadują ze sobą dokładnie wtedy, gdy różnią się pojedynczym bitem. Demisześcian może być skonstruowany z hipersześcianu jako wypukła powłoka podzbioru liczb binarnych o parzystej liczbie bitów niezerowych ( liczby złe ), a jej krawędzie łączą pary liczb, których odległość Hamminga wynosi dokładnie dwa.

Możliwe jest również skonstruowanie grafu sześciennego o połowę z niskowymiarowego grafu hipersześcianowego, bez pobierania podzbioru wierzchołków:

${\ Displaystyle {\ Frac {1} {2}} Q_ {n} = Q_ {n-1} ^ {2}}$

gdzie indeks górny 2 oznacza kwadrat grafu hipersześcianowego Q _{n  − 1} , grafu utworzonego przez połączenie par wierzchołków, których odległość wynosi co najwyżej dwa w oryginalnym grafie. Na przykład, wykres sześcianu połówkowego o wymiarze czwartym może być utworzony ze zwykłego trójwymiarowego sześcianu, zachowując krawędzie sześcianu i dodając krawędzie łączące pary wierzchołków, które znajdują się na przeciwległych rogach tej samej kwadratowej powierzchni.

Przykłady

Wykres sześcienny podzielony na pół o wymiarze 3 jest kompletnym wykresem K ₄ , wykresem czworościanu . Wykres sześcienny _połówkowy wymiaru 4 to K _2,2,2,2 , wykres czterowymiarowego regularnego polytope , 16-cell . Połowa wykresu sześciennego o wymiarze piątym jest czasami nazywany wykresem Clebscha i jest uzupełnieniem złożonego wykresu sześciennego o wymiarze piątym, który jest powszechnie nazywany wykresem Clebscha. Istnieje w 5-wymiarowym, jednolitym 5-politopie , 5-demicube . ${\displaystyle {\tfrac {1}{2}}Q_{3}}$ ${\displaystyle {\tfrac {1}{2}}Q_{4}}$${\displaystyle {\tfrac {1}{2}}Q_{5}}$

Nieruchomości

Ponieważ jest to dwudzielna połowa grafu o zależności od odległości , wykres sześcienny o połowę jest sam w sobie grafem o zależności od odległości. A ponieważ zawiera hipersześcian jako podgraf spinający , dziedziczy po hipersześcianie wszystkie własności grafu monotonicznego, takie jak własność zawierania cyklu Hamiltona .

Podobnie jak w przypadku grafów hipersześcianowych i ich izometrycznych (zachowujących odległość) podgrafów sześcianów cząstkowych , graf połówkowy sześcienny może być osadzony izometrycznie w rzeczywistej przestrzeni wektorowej za pomocą metryki Manhattanu ( funkcja odległości L ₁ ). To samo dotyczy izometrycznych podgrafów grafów sześciennych o połowę, które można rozpoznać w czasie wielomianowym ; tworzy to kluczową podprogram algorytmu, który sprawdza, czy dany wykres może być osadzony izometrycznie w metryce Manhattan.

Dla każdego wykresu sześciennego o wymiarze piątym lub większym możliwe jest (niewłaściwe) pokolorowanie wierzchołków dwoma kolorami w taki sposób, że wynikowy kolorowy wykres nie ma nietrywialnych symetrii. W przypadku wykresów o wymiarze trzecim i czwartym potrzebne są cztery kolory, aby wyeliminować wszystkie symetrie.

Sekwencja

Dwa pokazane wykresy są symetrycznymi rzutami wielokątów D _n i B _n Petriego (2( n  - 1) i n dwuściennej symetrii ) powiązanego wielotopu, który może zawierać nakładające się krawędzie i wierzchołki.

nie	Polytope	Wykres	Wierzchołki	Krawędzie
2	Odcinek		2	–
3	czworościan		4	6
4	16-ogniwowy		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

Bibliografia

Linki zewnętrzne

• Weisstein, Eric W. „Wykres o połowę sześcienny” . MatematykaŚwiat .