Граф призми

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Приклади

[ред. | ред. код]

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


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.

Література

[ред. | ред. код]