Многогранный граф - Polyhedral graph

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

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

Характеристика

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

Согласно с Теорема Стейница этих двух теоретико-графических свойств достаточно, чтобы полностью охарактеризовать многогранные графы: это в точности 3-вершинно-связанные плоские графы. То есть, если граф является как плоским, так и 3-вершинно-связным, существует многогранник, вершины и ребра которого образуют изоморфный график.[1][2] Для такого графа его представление в виде подразделения выпуклого многоугольника на более мелкие выпуклые многоугольники можно найти с помощью Вложение Тутте.[3]

Гамильтоничность и краткость

Тейт предположил что каждый кубический многогранный граф (то есть многогранный граф, в котором каждая вершина инцидентна ровно трем ребрам) имеет Гамильтонов цикл, но это предположение было опровергнуто контрпримером В. Т. Тутте, многогранная, но негамильтонова График Тутте. Если ослабить требование кубичности графа, негамильтоновы многогранные графы будут намного меньше. Граф с наименьшим количеством вершин и ребер - это 11-вершинный и 18-реберный Граф Гершеля,[4] а также существует негамильтонов многогранный граф с 11 вершинами, в котором все грани являются треугольниками, График Гольднера – Харари.[5]

Более того, существует постоянная α <1 ( показатель краткости ) и бесконечное семейство многогранных графов таких, что длина наибольшего простой путь из п-вершинного графа в семействе O (пα).[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 ).

Особые случаи

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

использованная литература

  1. ^ Лекции по многогранникам, от Гюнтер М. Циглер (1995) ISBN  0-387-94365-X , Глава 4 "Теорема Штейница для 3-многогранников", стр.103.
  2. ^ Грюнбаум, Бранко (2003), Выпуклые многогранники, Тексты для выпускников по математике, 221 (2-е изд.), Springer-Verlag, ISBN  978-0-387-40409-7.
  3. ^ Тутте, В. Т. (1963), «Как нарисовать график», Труды Лондонского математического общества, 13: 743–767, Дои:10.1112 / плмс / с3-13.1.743, Г-Н  0158387.
  4. ^ Вайсштейн, Эрик В. «График Гершеля». MathWorld..
  5. ^ Вайсштейн, Эрик В. "График Гольднера-Харари". MathWorld..
  6. ^ Вайсштейн, Эрик В. «Показатель краткости». MathWorld..
  7. ^ Грюнбаум, Бранко; Моцкин, Т. С. (1962), "Самые длинные простые пути в многогранных графах", Журнал Лондонского математического общества, s1-37 (1): 152–160, Дои:10.1112 / jlms / s1-37.1.152.
  8. ^ Duijvestijn, A. J. W. (1996), «Число полиэдральных (3-связных плоских) графов» (PDF), Математика вычислений, 65: 1289–1293, Дои:10.1090 / S0025-5718-96-00749-1.

внешние ссылки