График призмы

В математической области теории графов призменный граф — это граф является одна из призм , скелетом которого .

Примеры

Отдельные графики могут быть названы в честь соответствующего твердого тела:

Граф треугольной призмы – 6 вершин, 9 ребер.
Кубический граф – 8 вершин, 12 ребер.
пятиугольной призмы – 10 вершин, 15 ребер. Граф
Граф шестиугольной призмы – 12 вершин, 18 ребер.
Граф семиугольной призмы – 14 вершин, 21 ребро.
Граф восьмиугольной призмы – 16 вершин, 24 ребра.
...

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

Хотя геометрически звездчатые многоугольники также образуют грани другой последовательности (самопересекающихся и невыпуклых) призматических многогранников, графики этих звездчатых призм изоморфны графам призм и не образуют отдельную последовательность графов.

Строительство

Графы-призмы являются примерами обобщенных графов Петерсена с параметрами GP( n ,1). Их также можно построить как декартово произведение графа циклов с одним ребром. ^[1]

Как и многие вершинно-транзитивные графы, графы-призмы также могут быть построены как графы Кэли . порядка n Группа диэдра — это группа симметрий правильного n- угольника на плоскости; он действует на n -угольник посредством вращений и отражений. Он может быть сгенерирован двумя элементами: поворотом на угол 2 $π$ / n и одним отражением, а его граф Кэли с этим порождающим набором является графом-призмой. Абстрактно группа имеет презентацию $\langle r,f\mid r^{n},f^{2},(rf)^{2}\rangle$ (где r — вращение, а f — отражение или переворот), а граф Кэли имеет r и f (или r , r ⁻¹, и f ) как его генераторы. ^[1]

Графы n -угольных призм с нечетными значениями n можно построить как циркулянтные графы. $C_{2n}^{2,n}$ .Однако эта конструкция не работает для четных значений n . ^[1]

Характеристики

Граф n -угольной призмы имеет 2 n вершин и 3 n ребер. Это обычные кубические графы .Поскольку призма обладает симметрией, переводящей каждую вершину в другую вершину, графы призм являются вершинно-транзитивными графами .Как многогранные графы , они также являются 3-связными плоскими графами . Каждый граф-призма имеет гамильтонов цикл . ^[2]

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

Число остовных деревьев -угольного графа n призмы определяется формулой ^[4]

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

Для n = 3, 4, 5,... эти числа равны

75, 384, 1805, 8100, 35287, 150528, ... (последовательность A006235 в OEIS ).

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

Пятиугольная призма — один из запрещенных миноров для графов древовидной ширины три. ^[6] Граф треугольной призмы и куба имеет ширину дерева ровно три, но все более крупные графы-призмы имеют ширину дерева четыре.

Связанные графики

К другим бесконечным последовательностям графа многогранников, образованным аналогичным образом из многогранников с основаниями правильных многоугольников, относятся графы антипризм (графы антипризм ) и графы-колеса (графы пирамид ). Другие вершинно-транзитивные многогранные графы включают архимедовы графы .

Если два цикла призменного графа прерываются удалением одного ребра в одном и том же положении в обоих циклах, результатом является лестничный граф . Если эти два удаленных ребра заменить двумя скрещенными ребрами, в результате получится неплоский граф, называемый лестницей Мёбиуса . ^[7]

Ссылки

^ Перейти обратно: ^а ^б ^с Вайсштейн, Эрик В. «Призматический график» . Математический мир .
^ Рид, Р.К. и Уилсон, Р.Дж. Атлас графиков , Оксфорд, Англия: Oxford University Press, переиздание 2004 г., специальные графики главы 6, стр. 261, 270.
^ Эппштейн, Дэвид (2013), «Сложность построения трехмерных ортогональных графов без изгиба», Журнал графовых алгоритмов и приложений , 17 (1): 35–55, arXiv : 0709.4087 , doi : 10.7155/jgaa.00283 , MR 3019198 , S2CID 2716392 . Эппштейн приписывает наблюдение о том, что призменные графы имеют почти максимальное количество 1-факторизаций, личному сообщению Грега Куперберга .
^ Джагерс, А.А. (1988), «Заметка о количестве остовных деревьев в графе призмы», Международный журнал компьютерной математики , 24 (2): 151–154, doi : 10.1080/00207168808803639 .
^ Марк, Тилен (2015), Классификация вершинно-транзитивных кубических частичных кубов , arXiv : 1509.04565 , Bibcode : 2015arXiv150904565M .
^ Арнборг, Стефан; Проскуровский, Анджей; Корнейл, Дерек Г. (1990), «Запрещенные минорные характеристики частичных трехдеревьев», Discrete Mathematics , 80 (1): 1–19, doi : 10.1016/0012-365X(90)90292-P , MR 1045920 .
^ Гай, Ричард К .; Харари, Франк (1967), «На лестницах Мёбиуса», Canadian Mathematical Bulletin , 10 (4): 493–496, doi : 10.4153/CMB-1967-046-4 , MR 0224499 .

[mathworld-1] Перейти обратно: ^а ^б ^с Вайсштейн, Эрик В. «Призматический график» . Математический мир .

[2] Рид, Р.К. и Уилсон, Р.Дж. Атлас графиков , Оксфорд, Англия: Oxford University Press, переиздание 2004 г., специальные графики главы 6, стр. 261, 270.

[3] Эппштейн, Дэвид (2013), «Сложность построения трехмерных ортогональных графов без изгиба», Журнал графовых алгоритмов и приложений , 17 (1): 35–55, arXiv : 0709.4087 , doi : 10.7155/jgaa.00283 , MR 3019198 , S2CID 2716392 . Эппштейн приписывает наблюдение о том, что призменные графы имеют почти максимальное количество 1-факторизаций, личному сообщению Грега Куперберга .

[4] Джагерс, А.А. (1988), «Заметка о количестве остовных деревьев в графе призмы», Международный журнал компьютерной математики , 24 (2): 151–154, doi : 10.1080/00207168808803639 .

[5] Марк, Тилен (2015), Классификация вершинно-транзитивных кубических частичных кубов , arXiv : 1509.04565 , Bibcode : 2015arXiv150904565M .

[6] Арнборг, Стефан; Проскуровский, Анджей; Корнейл, Дерек Г. (1990), «Запрещенные минорные характеристики частичных трехдеревьев», Discrete Mathematics , 80 (1): 1–19, doi : 10.1016/0012-365X(90)90292-P , MR 1045920 .

[7] Гай, Ричард К .; Харари, Франк (1967), «На лестницах Мёбиуса», Canadian Mathematical Bulletin , 10 (4): 493–496, doi : 10.4153/CMB-1967-046-4 , MR 0224499 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]