Полиэдральный граф — неориентированный граф , образованный из вершин и рёбер выпуклого многогранника , или, в контексте теории графов — вершинно 3-связный планарный граф .

Описание

Диаграмма Шлегеля выпуклого многогранника представляет его вершины и рёбра как точки и отрезки на евклидовой плоскости , образуя разбиение внешнего выпуклого многоугольника на более мелкие выпуклые многоугольники. Диаграмма не имеет самопересечений, так что любой полиэдральный граф является также планарным . Кроме того, по теореме Балинского , этот граф является вершинно 3-связным .

Согласно теореме Штейница этих двух свойств достаточно, чтобы полностью описать полиэдральные графы — это в точности вершинно 3-связные планарные графы. Таким образом, если граф и планарен, и вершинно 3-связен, существует многогранник, вершины и рёбра которого образуют изоморфный исходному граф . Если задан такой граф, представление его в виде разбиения выпуклого многоугольника на меньшие выпуклые многоугольники может быть найдено с помощью вложение Татта .

Гамильтоновость и показатель короткости

Тэйт высказал гипотезу , что любой кубический полиэдральный граф (то есть полиэдральный граф, в котором каждая вершина инцидентна в точности трём рёбрам) имеет гамильтонов цикл , но эта гипотеза была опровергнута Уильямом Таттом , построившим контрпример — полиэдральный негамильтонов граф ( граф Татта ). Если ослабить условие, что граф должен быть кубическим, появится много других меньших по размерам негамильтоновых полиэдральных графов, один из них, имеющий 11 вершин и 18 рёбер — граф Хершеля , существует также негамильтонов полиэдральный граф с 11 вершинами, в котором все грани треугольны — граф Голднера — Харари .

Строго говоря, существует константа ${\displaystyle \alpha <1}$ ( показатель короткости ^{[ уточнить ]} ) и бесконечное семейство полиэдральных графов, таких что длина самого длинного простого пути графа с ${\displaystyle n}$ вершинами в семействе равна ${\displaystyle O(n^{\alpha })}$ .

Комбинаторное перечисление

В 1996 году определено число полиэдральных графов, имеющих до 26 рёбер , в частности, число таких графов с 6, 7, …, 21 рёбрами равно:

1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810 .

Можно также перечислить полиэдральные графы по числу их вершин, число таких графов равно:

1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, … .

Специальные случаи

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

Примечания

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .