Wykres pryzmatyczny

W matematycznej dziedzinie teorii grafów wykres pryzmowy to wykres , którego szkieletem jest jeden z pryzmatów .

Przykłady

Poszczególne wykresy mogą być nazwane na cześć powiązanej bryły:

pryzmatyczny trójkątny – 6 wierzchołków, 9 krawędzi
Graf sześcienny – 8 wierzchołków, 12 krawędzi
pryzmatyczny pięciokątny – 10 wierzchołków, 15 krawędzi
graniastosłupowy sześciokątny – 12 wierzchołków, 18 krawędzi
Siedmiokątny graf pryzmowy – 14 wierzchołków, 21 krawędzi
pryzmatowy ośmiokątny – 16 wierzchołków, 24 krawędzie
...

Y ₃ = GP(3,1)	Y ₄ = Q ₃ = GP(4,1)	Y ₅ = GP(5,1)	Y ₆ = GP(6,1)	Y ₇ = GP(7,1)	Y ₈ = GP(8,1)

Chociaż geometrycznie wielokąty gwiazdowe tworzą również ściany innej sekwencji (samoprzecinających się i nie wypukłych) wielościanów pryzmatycznych, wykresy tych pryzmatów gwiazdowych są izomorficzne z wykresami pryzmatycznymi i nie tworzą oddzielnej sekwencji wykresów.

Budowa

Wykresy pryzmowe są przykładami uogólnionych wykresów Petersena z parametrami GP( n ,1). Można je również skonstruować jako iloczyn kartezjański wykresu cyklu z pojedynczą krawędzią.

Podobnie jak w przypadku wielu grafów przechodnich przez wierzchołki, wykresy pryzmowe można również skonstruować jako wykresy Cayleya . Grupa dwuścienna rzędu n jest grupą symetrii foremnego n -gonu na płaszczyźnie; działa na n -gon poprzez obroty i odbicia. Może być wygenerowany przez dwa elementy, obrót o kąt 2 $π$ / n i pojedyncze odbicie, a jego wykres Cayleya z tym zespołem generującym jest wykresem pryzmatycznym. Abstrakcyjnie grupa ma prezentację ${\ Displaystyle \ langle r, f \ mid r ^ {n}, f ^ {2}, (rf) ^ {2} \ rangle}$ (gdzie r jest obrotem i f jest odbiciem lub odwróceniem), a wykres Cayleya ma r i f (lub r , r ^-1 i f ) jako generatory.

N -gonalne $o$ nieparzystych n skonstruować jako cyrkulacyjne Jednak ta konstrukcja nie działa dla parzystych wartości n .

Nieruchomości

Wykres n -gonalnego pryzmatu ma 2 n wierzchołków i 3 n krawędzi. Są to regularne , sześcienne wykresy . Ponieważ pryzmat ma symetrie łączące każdy wierzchołek z drugim wierzchołkiem, wykresy pryzmowe są wykresami przechodnimi wierzchołków . Jako grafy wielościenne są one również grafami planarnymi połączonymi trzema wierzchołkami . Każdy wykres pryzmatyczny ma cykl Hamiltona .

Spośród wszystkich dwuspójnych wykresów sześciennych , wykresy pryzmatyczne zawierają w granicach stałego współczynnika największą możliwą liczbę jednoczynnikowych rozkładów . Faktoryzacja 1 to podział zbioru krawędzi wykresu na trzy doskonałe dopasowania lub równoważnie kolorowanie krawędzi wykresu trzema kolorami. Każdy dwuspójny z n -wierzchołkami ma faktoryzację O (2 ^{n /2} ) 1, a wykresy pryzmowe mają faktoryzację Ω (2 ^{n /2} ) 1.

Liczbę drzew rozpinających n - gonalnego wykresu pryzmatycznego podaje wzór

{\ Displaystyle {\ Frac {n}} {\ bigl (} (2 + {\ sqrt {3}}) ^ { n}+(2-{\sqrt {3}})^{n}-2){\bigr .}}

Dla n = 3, 4, 5, ... te liczby są

75, 384, 1805, 8100, 35287, 150528, ... (sekwencja A006235 w OEIS ).

N - gonalne wykresy pryzmatyczne dla parzystych wartości n są częściowymi sześcianami . Tworzą jedną z niewielu znanych nieskończonych rodzin sześciennych sześcianów cząstkowych i (z wyjątkiem czterech sporadycznych przykładów) jedyne sześcienne sześciany cząstkowe przechodnie przez wierzchołki.

Pryzmat pięciokątny jest jedną z nieletnich zabronionych w grafach o szerokości drzewa trzy. Trójkątny pryzmat i wykres sześcienny mają szerokość drzewa dokładnie trzy, ale wszystkie większe wykresy pryzmatyczne mają szerokość drzewa cztery.

Powiązane wykresy

Inne nieskończone ciągi grafów wielościennych utworzonych w podobny sposób z wielościanów o podstawach wielokątów foremnych obejmują grafy antygraniastosłupowe (wykresy antygraniastosłupów ) i grafy kołowe (wykresy piramid ). Inne grafy wielościenne przechodnie przez wierzchołki obejmują wykresy Archimedesa .

Jeśli dwa cykle wykresu pryzmatycznego zostaną przerwane poprzez usunięcie pojedynczej krawędzi w tym samym położeniu w obu cyklach, otrzymamy wykres drabinkowy . Jeśli te dwie usunięte krawędzie zostaną zastąpione dwiema skrzyżowanymi krawędziami, powstanie niepłaski graf zwany drabiną Möbiusa .