Граф призми

У теорії графів граф призми — це граф, скелетом якого є одна із призм.

Приклади

Окремі графи можна назвати за асоційованими тілами:

• Граф трикутної призми — 6 вершин, ребер 9
• Кубічний граф — 8 вершин, ребер 12
• Граф п'ятикутної призми — 10 вершин, ребер 15
• Граф шестикутної призми — 12 вершин, ребер 18
• Граф Шаблон:Не перекладено — 14 вершин, ребер 21
• Граф восьмикутної призми — 16 вершин, ребер 24
• …

Y3 = GP(3,1)

Y4 = Q3 = GP(4,1)

Y5 = GP(5,1)

Y6 = GP(6,1)

Y7 = GP(7,1)

Y8 = GP(8,1)

Хоча геометрично зірчасті багатокутники також є гранями іншої послідовності (самоперетинних і неопуклих) призматичних багатогранників, графи цих зірчастих призм ізоморфні графам призм і не утворюють окремої послідовності графів.

Побудова

Графи призм є прикладами узагальнених графів Петерсена з параметрами GP(n,1). Графи також можна утворити як прямий добуток циклу і одиничного ребра.

Як і багато вершинно-транзитивних графи, призматичні графи можна побудувати як граф Келі. Діедральна група порядку n є групою симетрій правильного n-кутника на площині. Вона діє на n-кутник обертаннями і відбиттями. Групу можна згенерувати двома елементами: обертанням на кут $2\pi /n$ і одним відбиттям, і граф Келі цієї групи з цією генерувальною множиною є графом призми. Абстрактно група має задання $⟨r,f\mid r^n,f^2,(rf{)}^2⟩$ (де r — це обертання, а f — відбиття) і граф Келі має генератори r і f (або r, r⁻¹ і f).

Граф n-кутної призми з непарним n можна побудувати як циркулянтний граф $C_{2n}^{2,n}$, однак ця побудова не працює для парних значень n.

Властивості

Граф n-кутної призми має 2n вершин і 3n ребер. Графи є регулярними кубічними графами. Оскільки призма має симетрії, які переводять будь-яку вершину в будь-яку іншу, графи призм є вершинно-транзитивними графами. Як поліедральні графи, ці графи також є вершинно 3-зв'язними планарними графами. Будь-який граф призми має гамільтонів циклШаблон:Sfn.

Серед усіх двозв'язних кубічних графів графи призм мають з точністю до сталого множника найбільше можливе число 1-розкладень графу. 1-розкладення — це розбиття множини ребер графу на три досконалих парування, або, еквівалентно, реберне розфарбування графу трьома кольорами. Будь-який двозв'язний кубічний граф з n вершинами має O(2^n/2) 1-розкладень, а граф призми має Ω(2^n/2) 1-розкладень.

Число кістякових дерев графу n-кутної призми задається формулоюШаблон:Sfn:

$\frac{n}{2}((2+\sqrt{3}{)}^n+(2-\sqrt{3}{)}^n)$

Для n = 3, 4, 5, … ці числа рівні

78, 388, 1810, 8106, 35294, …

Графи n-кутних призм для парних n є частковими кубами. Вони утворюють одне з небагатьох відомих нескінченних сімейств кубічних графів часткових кубів, і вони є (за винятком чотирьох випадків) єдиними вершинно-транзитивними кубічними частковими кубамиШаблон:Sfn.

Граф п'ятикутної призми є одним із заборонених мінорів для графів з деревною шириною триШаблон:Sfn. Графи трикутної призми і куба мають деревну ширину рівно три, але всі великі призми мають деревну ширину чотири.

Пов'язані графи

Інші нескінченні сімейства поліедральних графів, засновані подібним чином з багатогранників з правильними основами: Шаблон:Не перекладено і колеса (графи пірамід). Іншими вершинно-транзитивними поліедральними графами є архімедові графи.

Якщо два цикли призматичного графу розірвати видаленням одного ребра в одному і тому ж місці в обох циклах, отримаємо драбину. Якщо два видалених ребра замінити двома перехрещеними ребрами, отримаємо непланарний граф «драбина Мебіуса»Шаблон:Sfn.

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга