В геометрической теории графов , разделе математики , многогранный граф — это неориентированный граф, образованный из вершин и ребер выпуклого многогранника . Альтернативно, чисто в терминах теории графов, многогранные графы представляют собой 3-связные плоские графы .
Диаграмма Шлегеля выпуклого многогранника представляет его вершины и ребра в виде точек и отрезков евклидовой плоскости , образуя подразделение внешнего выпуклого многоугольника на меньшие выпуклые многоугольники ( выпуклый рисунок графика многогранника). Он не имеет пересечений, поэтому каждый многогранный граф также является плоским графом . Кроме того, по теореме Балинского , это 3-вершинно-связный граф .
Согласно теореме Стейница , этих двух теоретико-графовых свойств достаточно, чтобы полностью охарактеризовать многогранные графы: они в точности представляют собой 3-связные плоские графы. То есть, если граф одновременно плоский и 3-связный, существует многогранник, вершины и ребра которого образуют изоморфный граф . [1] [2] Учитывая такой граф, его представление в виде подразделения выпуклого многоугольника на меньшие выпуклые многоугольники можно найти с помощью вложения Тутта . [3]
Тейт предположил , что каждый кубический многогранный граф (то есть многогранный граф, в котором каждая вершина инцидентна ровно трем ребрам) имеет гамильтонов цикл , но эта гипотеза была опровергнута контрпримером WT Tutte , многогранного, но не гамильтонова графа Тутта. . Если ослабить требование кубичности графа, появятся негамильтоновы многогранные графы гораздо меньшего размера. Граф с наименьшим количеством вершин и ребер — это граф Гершеля с 11 вершинами и 18 рёбрами , [4] , а также существует негамильтонов многогранный граф с 11 вершинами, в котором все грани являются треугольниками, граф Гольднера–Харири . [5]
Более строго, существует константа ( показатель краткости ) и бесконечное семейство многогранных графов, такое что длина самого длинного простого пути графа с -вершинами в семействе равна . [6] [7]
Duijvestijn обеспечивает подсчет многогранных графов с числом ребер до 26; [8] Число этих графов с 6, 7, 8, ... ребрами равно
Можно также нумеровать многогранные графы по количеству вершин: для графов с 4, 5, 6, ... вершинами количество многогранных графов равно
Многогранный граф — это график простого многогранника , если он кубический (каждая вершина имеет три ребра), и граф симплициального многогранника , если он является максимальным плоским графом . Графы Халина , графы, образованные из плоского вложенного дерева путем добавления внешнего цикла, соединяющего все листья дерева, образуют еще один важный подкласс многогранных графов.