Полиэдральный граф

Полиэдральный граф, образованный как диаграмма Шлегеля из правильного додекаэдра.

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

Описание

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

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

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

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

Строго говоря, существует константа $\alpha <1$ (показатель короткости^{[уточнить]}) и бесконечное семейство полиэдральных графов, таких что длина самого длинного простого пути графа с $n$ вершинами в семействе равна $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. Polyhedral Graph (англ.) на сайте Wolfram MathWorld.