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

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

Примеры

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

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

Y₃ = GP (3,1)	Y₄ = Q₃ = GP (4,1)	Y₅ = GP (5,1)	Y₆ = GP (6,1)	Y₇ = GP (7,1)	Y₈ = 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]

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

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

[mathworld-1] а ^б ^c Вайсштейн, Эрик В. «График призмы». 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]