Багатогранний граф
Багатогра́нний граф, або поліедра́льний граф — неорієнтований граф, утворений з вершин і ребер опуклого многогранника, або, в контексті теорії графів — 3-вершинно-зв'язний планарний граф.
Опис
Діаграма Шлегеля опуклого многогранника подає його вершини і ребра як точки і відрізки на евклідовій площині, утворюючи розбиття зовнішнього опуклого багатокутника на дрібніші опуклі багатокутники. Діаграма не має самоперетинів, так що будь-який багатогранний граф є планарним. Крім того, за Шаблон:Нп, цей граф є 3-вершинно-зв'язним.
Згідно з теоремою Штайніца цих двох властивостей достатньо, щоб повністю описати багатогранні графи — це є саме 3-вершинно-зв'язні планарні графи. Таким чином, якщо граф і планарний, і 3-вершинно-звязний, існує многогранник, вершини і ребра якого утворюють граф, ізоморфний початковому[1][2]. Якщо задано такий граф, подання його у вигляді розбиття опуклого багатокутника на менші опуклі багатокутники може бути знайдене за допомогою вкладення Татта[3].
Гамільтоновість і показник короткості
Шаблон:Див. також Тейт висловив гіпотезу, що будь-який кубічний багатогранний граф (тобто багатогранний граф, у якому кожна вершина інцидентна рівно трьом ребрам) має гамільтонів цикл, але цю гіпотезу було спростовано Вільямом Таттом, який побудував контрприклад — багатогранний негамільтонів граф (граф Татта). Якщо послабити умову, що граф повинен бути кубічним, з'явиться багато інших менших за розмірами негамільтонових багатогранних графів, один з них, який має 11 вершин і 18 ребер — граф Гершеля[4]. Існує також негамільтонів багатогранний граф з 11 вершинами, в якому всі грані трикутні — граф Голднера — Харарі[5].
Строго кажучи, існує константа (показник короткості) і нескінченна родина багатогранних графів, таких що довжина найдовшого простого шляху графу з вершинами в родині дорівнює [6][7].
Комбінаторне перерахування
У 1996 році визначено число багатогранних графів, що мають до 26 ребер[8], зокрема, число таких графів з 6, 7, …, 21 ребрами дорівнює:
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810[9].
Можна також перерахувати багатогранні графи за кількістю їхніх вершин, число таких графів дорівнює:
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, …[10].
Спеціальні випадки
Багатогранний граф — граф простого многогранника, якщо він є кубічним (в кожній вершині сходяться три ребра), і це граф симпліційного многогранника, якщо він є максимальним планарним графом. Графи Халіна, утворені з планарних дерев шляхом додавання зовнішнього циклу, що проходить через всі листки дерева, утворюють інший важливий підклас багатогранних графів.