График призмы - Prism graph

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

Примеры

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

• Треугольная призма граф - 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 (п, 1). Они также могут быть построены как Декартово произведение из график цикла с одинарным краем.^[1]

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

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

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

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

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

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

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

За п = 3, 4, 5, ... эти числа

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

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

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

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

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

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

Рекомендации

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