Wykres sześcianu o połowę

Wykres kostki o połowę
Wykres kostki o połowę 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	Symetryczna odległość regularna
Notacja	1 / 2 Q n
Tabela wykresów i parametrów

Budowa dwóch półsześcianów (czworościanów foremnych tworzących stella octangula ) z jednego sześcianu. Graf sześcianu podzielonego na pół wymiaru trzeciego to wykres wierzchołków i krawędzi pojedynczego półsześcianu. Przekrojony na pół wykres sześcianu wymiaru czwartego zawiera wszystkie wierzchołki i krawędzie sześcianu oraz wszystkie krawędzie dwóch półsześcianów.

W teorii grafów graf półsześcianu lub wykres połowy sześcianu wymiaru n jest wykresem półhipersześcianu , utworzonym przez połączenie par wierzchołków w odległości dokładnie dwóch od siebie na grafie hipersześcianu . Oznacza to, że jest to pół kwadratu hipersześcianu. Ten wzorzec łączności tworzy dwa izomorficzne grafy , odłączone od siebie, z których każdy jest przepołowionym wykresem sześciennym.

Konstrukcje równoważne

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

Możliwe jest również skonstruowanie podzielonego na pół wykresu sześciennego z niskowymiarowego wykresu hipersześcianu, 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ścianu Q _{n − 1} , wykresu utworzonego przez połączenie par wierzchołków, których odległość w oryginalnym grafie wynosi co najwyżej dwa. Na przykład przepołowiony wykres sześcianu o wymiarze czwartym można utworzyć ze zwykłego trójwymiarowego sześcianu, zachowując krawędzie sześcianu i dodając krawędzie łączące pary wierzchołków znajdujących się w przeciwległych rogach tej samej kwadratowej ściany.

Przykłady

$Przekrojony$ wykres kostki wymiaru 3 to wykres K ₄ , czworościanu . Przekrojony na pół wykres $wykres$ ₄ K , czterowymiarowej regularnej polytope , 16-ogniwowy . Wykres kostki podzielonej na pół ${\ Displaystyle {\ tfrac {1}{2}} Q_ {5}}$ wymiaru piątego jest czasami nazywany wykresem Clebscha i jest uzupełnieniem złożonego wykresu sześciennego wymiaru piątego, który jest częściej nazywany Wykres Clebscha. Istnieje w 5-wymiarowym jednolitym 5-polytopie , 5-półsześcianie .

Nieruchomości

Ponieważ jest to dwudzielna połowa wykresu regularnego odległości , przepołowiony wykres sześcienny sam jest regularny odległościowo. A ponieważ zawiera hipersześcian jako rozpinający podgraf , dziedziczy z hipersześcianu wszystkie właściwości grafu monotonicznego, takie jak właściwość zawierania cyklu Hamiltona .

Podobnie jak w przypadku wykresów hipersześcianu i ich izometrycznych (zachowujących odległość) podgrafów kostek cząstkowych , wykres sześcianu o połowę można osadzić 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 ; stanowi to kluczową procedurę dla algorytmu, który sprawdza, czy dany wykres można osadzić izometrycznie w metryce Manhattanu.

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

Sekwencja

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

N	Politop	Wykres	Wierzchołki	Krawędzie
2	Odcinek		2	–
3	czworościan		4	6
4	16-ogniwowy		8	24
5	5-sześcian		16	80
6	6-sześcian		32	240
7	7-sześcian		64	672
8	8-sześcian		128	1792
9	9-sześcian		256	4608
10	10-sześcian		512	11520

Linki zewnętrzne

• Weisstein, Eric W. „Wykres kostki o połowę” . MathWorld .