Граф при́змы — рёберный граф одной из призм.
Примеры Индивидуальные графы можно назвать согласно ассоциированным телам:
Граф треугольной призмы — 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(n,1). Графы также можно образовать как прямое произведение цикла и единичного ребра.
Как и многие вершинно-транзитивные графы, призматические графы можно построить как графы Кэли. Диэдральная группа порядка n является группой симметрий правильного n-угольника на плоскости. Она действует на n-угольник вращениями и отражениями. Группа может быть сгенерирована двумя элементами, вращением на угол и одним отражением, и граф Кэли этой группы с этим генерирующим множеством является графом призмы. Абстрактно группа имеет задание (где r — это вращение, а f — отражение) и граф Кэли имеет r и f (или r, r−1 и f) в качестве генераторов
Граф n-угольной призмы с нечётным n можно построить как циркулянтный граф , однако это построение не работает для чётных значений n.
Свойства Граф n-угольной призмы имеет 2n вершин и 3n рёбер. Графы являются регулярными кубическими графами. Поскольку призма имеет симметрии, переводящие любую вершину в любую другую, графы призм являются вершинно-транзитивными графами. Являясь полиэдральными графами, эти графы также являются вершинно 3-связными планарными графами. Любой граф призмы имеет гамильтонов цикл.
Среди всех двусвязных кубических графов графы призм имеют с точностью до постоянного множителя наибольшее возможное число 1-разложений графа. 1-разложение — это разбиение множества рёбер графа на три совершенных паросочетания, или, эквивалентно, рёберная раскраска графа тремя цветами. Любой двусвязный кубический граф с n вершинами имеет O(2n/2) 1-разложений, а граф призмы имеет Ω(2n/2) 1-разложений. Эппштейн приписывает наблюдение, что графы призм имеют близкое к максимальному число 1-разложений , высказавшему это наблюдение в частной беседе..
Число остовных деревьев графа n-угольной призмы задаётся формулой .
Для n = 3, 4, 5, … эти числа равны 78, 388, 1810, 8106, 35294, …
Графы n-угольных призм для чётных n являются частичными кубами. Они образуют одно из немногих известных бесконечных семейств кубических графов частичных кубов, и они являются (за исключением четырёх случаев) единственными вершинно-транзитивными кубическими частичными кубами.
Граф пятиугольной призмы является одним из запрещённых миноров для графов с древовидной шириной три. Графы треугольной призмы и куба имеют древовидную ширину в точности три, но все бо́льшие призмы имеют древовидную ширину четыре.
Связанные графы Другие бесконечные семейства полиэдральных графов, основанные подобным же образом из многогранников с правильными основаниями, включают и колёса (графы пирамид). Другими вершинно-транзитивными полиэдральными графами являются архимедовы графы.
Если два цикла призматического графа разорвать удалением одного ребра в одном и том же месте в обоих циклах, получим лестницу. Если два удалённых ребра заменить двумя скрещивающимися рёбрами, получим непланарный граф «Лестница Мёбиуса».
Примечания
Литература
Категория:Семейства графов Категория:Регулярные графы Категория:Планарные графы