Граф призми

граф, скелетом якого є одна із призм

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

Приклади ред.

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

 
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)[1].

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

Властивості ред.

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

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

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

 

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

78, 388, 1810, 8106, 35294, …

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

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

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

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

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

Примітки ред.

  1. Weisstein, Eric W. Граф призми(англ.) на сайті Wolfram MathWorld.
  2. Read, Wilson, 2004, с. 261, 270.
  3. Eppstein, 2013. Епштейн приписує спостереження, що графи призм мають близьке до максимального число 1-розкладень Грегу Купербергу[en], який висловив це спостереження в приватній бесіді.
  4. Jagers, 1988, с. 151–154.
  5. Marc, 2015.
  6. Arnborg, Proskurowski, Corneil, 1990, с. 1–19.
  7. Guy, Harary, 1967, с. 493–496.

Література ред.