В геометрической теории графов , ветвь математики , А многогранный граф является неориентированным граф формируется из вершин и ребер выпуклого многогранника . В качестве альтернативы, в чисто теоретико-графических терминах, многогранные графы представляют собой 3-вершинно-связанные плоские графы .
Характеристика [ править ]
Диаграмма Шлегель выпуклого многогранника представляет его вершины и ребра , как точки и отрезки , в евклидовой плоскости , образуя разбиение внешнего выпуклого многоугольника на более мелкие выпуклые многоугольники (а выпуклый рисунок графа многогранника). Он не имеет пересечений, поэтому любой многогранный граф также является плоским графом . Кроме того, по теореме Balinski в , это 3-вершина-связный граф .
Согласно теореме Стейница , этих двух теоретико-графических свойств достаточно, чтобы полностью охарактеризовать многогранные графы: это в точности 3-вершинно-связанные плоские графы. То есть, когда граф является как плоским, так и 3-вершинно-связным, существует многогранник, вершины и ребра которого образуют изоморфный граф. [1] [2] Для такого графа его представление как подразделение выпуклого многоугольника на более мелкие выпуклые многоугольники можно найти с помощью вложения Тутте . [3]
Гамильтонность и краткость [ править ]
Тейт предположил, что каждый кубический многогранный граф (то есть многогранный граф, в котором каждая вершина инцидентна ровно трем ребрам) имеет гамильтонов цикл , но эта гипотеза была опровергнута контрпримером В. Т. Тутте , многогранным, но негамильтоновым графом Тутте . Если ослабить требование кубичности графа, негамильтоновы многогранные графы будут намного меньше. Граф с наименьшим числом вершин и ребер является 11-вершиной и 18-края Хершель график , [4] , а также существует 11-вершина негамильтонова многогранное граф , в котором все грани треугольники, тем Голднер-Харари графа . [5]
Более того, существует постоянная α <1 (показатель краткости ) и бесконечное семейство многогранных графов такие, что длина самого длинного простого пути графа с n- вершинами в этом семействе равна O ( n α ). [6] [7]
Комбинаторное перечисление [ править ]
Duijvestijn обеспечивает подсчет многогранных графов до 26 ребер; [8] Количество этих графов с 6, 7, 8, ... ребрами равно
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (последовательность A002840 в OEIS ).
Можно также пронумеровать многогранные графы по их количеству вершин: для графов с 4, 5, 6, ... вершинами количество многогранных графов равно
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... (последовательность A000944 в OEIS ).
Особые случаи [ править ]
Многогранный граф - это граф простого многогранника, если он кубический (каждая вершина имеет три ребра), и граф симплициального многогранника, если он является максимальным плоским графом . На графиках Halin , графики , сформированные из плоского вложенного дерева , добавляя внешний цикл , соединяющий все из листьев дерева, образуют еще один важный подкласс многогранных графов.
Ссылки [ править ]
- ^ Лекции по многогранникам , Гюнтер М. Циглер (1995) ISBN 0-387-94365-X , глава 4 «Теорема Штейница для 3-многогранников», стр.103.
- ^ Грюнбаум, Бранко (2003), Выпуклые многогранники , Тексты для выпускников по математике , 221 (2-е изд.), Springer-Verlag, ISBN 978-0-387-40409-7.
- ^ Tutte, WT (1963), «Как нарисовать график», Proceedings of the London Mathematical Society , 13 : 743–767, doi : 10.1112 / plms / s3-13.1.743 , MR 0158387 .
- ^ Вайсштейн, Эрик В. "График Гершеля" . MathWorld . .
- ^ Weisstein, Эрик В. "График Гольднера-Харари" . MathWorld . .
- ^ Weisstein, Эрик В. "Показатель краткости" . MathWorld . .
- ^ Грюнбаум, Бранко ; Моцкин, TS (1962), "длинные простые пути в многогранных графов", журнал Лондонского математического общества , s1-37 (1): 152-160, DOI : 10.1112 / jlms / s1-37.1.152.
- ^ Duijvestijn, AJW (1996), "Число многогранных (3-связных плоских) графов" (PDF) , Математика вычислений , 65 : 1289–1293, DOI : 10.1090 / S0025-5718-96-00749-1 .
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. «Многогранный граф» . MathWorld .
