Багатогра́нний граф, або поліедра́льний граф — неорієнтований граф, утворений з вершин і ребер опуклого многогранника, або, в контексті теорії графів — 3-вершинно-зв'язний планарний граф.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWlMMkl4TDBSdlpHVmpZV2hsWkhKdmJsOXpZMmhzWldkbGJDNXpkbWN2TWpJd2NIZ3RSRzlrWldOaGFHVmtjbTl1WDNOamFHeGxaMlZzTG5OMlp5NXdibWM9LnBuZw==.png)
Опис
Діаграма Шлегеля опуклого многогранника подає його вершини і ребра як точки і відрізки на евклідовій площині, утворюючи розбиття зовнішнього опуклого багатокутника на дрібніші опуклі багатокутники. Діаграма не має самоперетинів, так що будь-який багатогранний граф є планарним. Крім того, за [ru], цей граф є 3-вершинно-зв'язним.
Згідно з (теоремою Штайніца) цих двох властивостей достатньо, щоб повністю описати багатогранні графи — це є саме 3-вершинно-зв'язні планарні графи. Таким чином, якщо граф і планарний, і 3-вершинно-звязний, існує многогранник, вершини і ребра якого утворюють граф, ізоморфний початковому. Якщо задано такий граф, подання його у вигляді розбиття опуклого багатокутника на менші опуклі багатокутники може бути знайдене за допомогою (вкладення Татта).
Гамільтоновість і показник короткості
Тейт висловив гіпотезу, що будь-який кубічний багатогранний граф (тобто багатогранний граф, у якому кожна вершина інцидентна рівно трьом ребрам) має гамільтонів цикл, але цю гіпотезу було спростовано Вільямом Таттом, який побудував контрприклад — багатогранний негамільтонів граф ((граф Татта)). Якщо послабити умову, що граф повинен бути кубічним, з'явиться багато інших менших за розмірами негамільтонових багатогранних графів, один з них, який має 11 вершин і 18 ребер — (граф Гершеля). Існує також негамільтонів багатогранний граф з 11 вершинами, в якому всі грані трикутні — граф Голднера — Харарі.
Строго кажучи, існує константа ((показник короткості)) і нескінченна родина багатогранних графів, таких що довжина найдовшого простого шляху графу з
вершинами в родині дорівнює
.
Комбінаторне перерахування
У 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, ….
Спеціальні випадки
Багатогранний граф — граф простого многогранника, якщо він є кубічним (в кожній вершині сходяться три ребра), і це граф симпліційного многогранника, якщо він є максимальним планарним графом. Графи Халіна, утворені з планарних дерев шляхом додавання зовнішнього циклу, що проходить через всі листки дерева, утворюють інший важливий підклас багатогранних графів.
Примітки
- Günter M. Ziegler. Lectures on Polytopes. — 1995. — С. 103, Глава 4 "Steinitz' Theorem for 3-Polytopes". — .
- Branko Grünbaum. Convex Polytopes. — Springer-Verlag, 2003. — Т. 221. — (Graduate Texts in Mathematics). — .
- W. T. Tutte. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — DOI: .
- Weisstein, Eric W. Граф Гершеля(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Goldner-Harary Graph(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Shortness Exponent(англ.) на сайті Wolfram MathWorld.
- Branko Grünbaum, T. S. Motzkin. Longest simple paths in polyhedral graphs // Journal of the London Mathematical Society. — 1962. — Т. s1-37, вип. 1. — С. 152–160. — DOI: .
- A. J. W. Duijvestijn. The number of polyhedral (3-connected planar) graphs // Mathematics of Computation. — 1996. — Т. 65. — С. 1289–1293. — DOI: .
- послідовність A002840 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
- послідовність A000944 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
Посилання
- Weisstein, Eric W. Polyhedral Graph(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет