У теорії графів граф призми — це граф, скелетом якого є одна із призм.
Приклади Окремі графи можна назвати за асоційованими тілами:
Граф трикутної призми — 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-кутник обертаннями і відбиттями. Групу можна згенерувати двома елементами: обертанням на кут і одним відбиттям, і граф Келі цієї групи з цією генерувальною множиною є графом призми. Абстрактно група має задання (де r — це обертання, а f — відбиття) і граф Келі має генератори r і f (або r, r−1 і f).
Граф n-кутної призми з непарним n можна побудувати як циркулянтний граф , однак ця побудова не працює для парних значень n.
Властивості Граф n-кутної призми має 2n вершин і 3n ребер. Графи є регулярними кубічними графами. Оскільки призма має симетрії, які переводять будь-яку вершину в будь-яку іншу, графи призм є вершинно-транзитивними графами. Як поліедральні графи, ці графи також є вершинно 3-зв'язними планарними графами. Будь-який граф призми має гамільтонів цикл.
Серед усіх двозв'язних кубічних графів графи призм мають з точністю до сталого множника найбільше можливе число 1-розкладень графу. 1-розкладення — це розбиття множини ребер графу на три досконалих парування, або, еквівалентно, реберне розфарбування графу трьома кольорами. Будь-який двозв'язний кубічний граф з n вершинами має O(2n/2) 1-розкладень, а граф призми має Ω(2n/2) 1-розкладень. Епштейн приписує спостереження, що графи призм мають близьке до максимального число 1-розкладень , який висловив це спостереження в приватній бесіді..
Число кістякових дерев графу n-кутної призми задається формулою:
Для n = 3, 4, 5, … ці числа рівні
78, 388, 1810, 8106, 35294, …
Графи n-кутних призм для парних n є частковими кубами. Вони утворюють одне з небагатьох відомих нескінченних сімейств кубічних графів часткових кубів, і вони є (за винятком чотирьох випадків) єдиними вершинно-транзитивними кубічними частковими кубами.
Граф п'ятикутної призми є одним із заборонених мінорів для графів з деревною шириною три. Графи трикутної призми і куба мають деревну ширину рівно три, але всі великі призми мають деревну ширину чотири.
Пов'язані графи Інші нескінченні сімейства поліедральних графів, засновані подібним чином з багатогранників з правильними основами: і колеса (графи пірамід). Іншими вершинно-транзитивними поліедральними графами є архімедові графи.
Якщо два цикли призматичного графу розірвати видаленням одного ребра в одному і тому ж місці в обох циклах, отримаємо драбину. Якщо два видалених ребра замінити двома перехрещеними ребрами, отримаємо непланарний граф «драбина Мебіуса».
Примітки
Література