Багатогранний граф: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
Вилучено вміст Додано вміст
правопис
Рядок 1: Рядок 1:
[[Файл:Dodecahedron_schlegel_diagram.png|міні|Багатогранний граф, утворений як {{нп|Діаграма Шлегеля|діаграма Шлегеля|ru|Диаграмма Шлегеля}} з {{нп|Правильний додекаедр|правильного додекаедра|ru|Правильный додекаэдр}}.]]
[[Файл:Dodecahedron_schlegel_diagram.png|міні|Багатогранний граф, утворений як {{нп|Діаграма Шлегеля|діаграма Шлегеля|ru|Диаграмма Шлегеля}} з {{нп|Правильний додекаедр|правильного додекаедра|ru|Правильный додекаэдр}}.]]
'''Багатогранний граф''' (або '''поліедральний граф''') — [[Граф (математика)|неорієнтований граф]], утворений з вершин і ребер [[Опуклий політоп|опуклого багатогранника]], або, в контексті теорії графів — [[K-вершинно-зв'язний граф|3-вершинно-зв'язний]] [[Планарний граф|планарний граф]].
'''Багатогра́нний граф''', або '''поліедра́льний граф''' — [[Граф (математика)|неорієнтований граф]], утворений з вершин і ребер [[Опуклий політоп|опуклого багатогранника]], або, в контексті теорії графів — [[K-вершинно-зв'язний граф|3-вершинно-зв'язний]] [[Планарний граф|планарний граф]].


== Опис ==
== Опис ==
Рядок 8: Рядок 8:


== Гамільтоновість і показник короткості ==
== Гамільтоновість і показник короткості ==
Тейт висловив {{нп|Гіпотеза Тейта (теорія графів)|гіпотезу|ru|Гипотеза Тэйта (теория графов)}}, що будь-який [[Кубічний граф|кубічний]] багатогранний граф (тобто багатогранний граф, у якому кожна вершина інцидентна рівно трьом ребрам) має [[Гамільтонів граф|гамільтонів цикл]], але цю гіпотезу було спростовано [[Віллем Татт|Вільямом Таттом]], який побудував контрприклад — багатогранний негамільтонів граф ([[Граф Татта|граф Татта]]). Якщо послабити умову, що граф повинен бути кубічним, з'явиться багато інших менших за розмірами негамільтонових багатогранних графів, один з них, який має 11 вершин і 18 ребер — {{нп|Граф Хершеля|граф Хершеля|ru|Граф Хершеля}}<ref>{{mathworld|title=Herschel Graph|urlname=HerschelGraph}}</ref>. Існує також негамільтонів багатогранний граф з 11 вершинами, в якому всі грані трикутні — {{нп|Граф Голднера — Харари|граф Голднера — Харарі|ru|Граф Голднера — Харари}}<ref>{{mathworld|title=Goldner-Harary Graph|urlname=Goldner-HararyGraph}}</ref>.
Тейт висловив {{нп|Гіпотеза Тейта (теорія графів)|гіпотезу|ru|Гипотеза Тэйта (теория графов)}}, що будь-який [[Кубічний граф|кубічний]] багатогранний граф (тобто багатогранний граф, у якому кожна вершина інцидентна рівно трьом ребрам) має [[Гамільтонів граф|гамільтонів цикл]], але цю гіпотезу було спростовано [[Вільям Татт|Вільямом Таттом]], який побудував контрприклад — багатогранний негамільтонів граф ([[Граф Татта|граф Татта]]). Якщо послабити умову, що граф повинен бути кубічним, з'явиться багато інших менших за розмірами негамільтонових багатогранних графів, один з них, який має 11 вершин і 18 ребер — {{нп|Граф Хершеля|граф Хершеля|ru|Граф Хершеля}}<ref>{{mathworld|title=Herschel Graph|urlname=HerschelGraph}}</ref>. Існує також негамільтонів багатогранний граф з 11 вершинами, в якому всі грані трикутні — {{нп|Граф Голднера — Харари|граф Голднера — Харарі|ru|Граф Голднера — Харари}}<ref>{{mathworld|title=Goldner-Harary Graph|urlname=Goldner-HararyGraph}}</ref>.


Строго кажучи, існує константа <math>\alpha < 1</math> (''{{нп|Показник короткості|показник короткості|ru|Показатель короткости}}''{{уточнити}}) і нескінченна родина багатогранних графів, таких що довжина найдовшого [[Шлях (теорія графів)|простого шляху]] графа з <math>n</math> вершинами в родині дорівнює <math>O(n^\alpha)</math><ref>{{mathworld|title=Shortness Exponent|urlname=ShortnessExponent}}</ref><ref>{{стаття
Строго кажучи, існує константа <math>\alpha < 1</math> (''{{нп|Показник короткості|показник короткості|ru|Показатель короткости}}''{{уточнити}}) і нескінченна родина багатогранних графів, таких що довжина найдовшого [[Шлях (теорія графів)|простого шляху]] графа з <math>n</math> вершинами в родині дорівнює <math>O(n^\alpha)</math><ref>{{mathworld|title=Shortness Exponent|urlname=ShortnessExponent}}</ref><ref>{{стаття

Версія за 22:55, 18 червня 2019

Багатогранний граф, утворений як діаграма Шлегеля з правильного додекаедра.

Багатогра́нний граф, або поліедра́льний графнеорієнтований граф, утворений з вершин і ребер опуклого багатогранника, або, в контексті теорії графів — 3-вершинно-зв'язний планарний граф.

Опис

Діаграма Шлегеля опуклого багатогранника подає його вершини і ребра як точки і відрізки на евклідовій площині, утворюючи розбиття зовнішнього опуклого багатокутника на дрібніші опуклі багатокутники. Діаграма не має самоперетинів, так що будь-який багатогранний граф є планарним. Крім того, за теоремою Балінського[ru], цей граф є 3-вершинно-зв'язним.

Згідно з теоремою Штайніца цих двох властивостей достатньо, щоб повністю описати багатогранні графи — це є саме 3-вершинно-зв'язні планарні графи. Таким чином, якщо граф і планарний, і 3-вершинно-звязний, існує багатогранник, вершини і ребра якого утворюють граф, ізоморфний початковому[1][2]. Якщо задано такий граф, подання його у вигляді розбиття опуклого багатокутника на менші опуклі багатокутники може бути знайдене за допомогою вкладення Татта[3].

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

Тейт висловив гіпотезу[ru], що будь-який кубічний багатогранний граф (тобто багатогранний граф, у якому кожна вершина інцидентна рівно трьом ребрам) має гамільтонів цикл, але цю гіпотезу було спростовано Вільямом Таттом, який побудував контрприклад — багатогранний негамільтонів граф (граф Татта). Якщо послабити умову, що граф повинен бути кубічним, з'явиться багато інших менших за розмірами негамільтонових багатогранних графів, один з них, який має 11 вершин і 18 ребер — граф Хершеля[4]. Існує також негамільтонів багатогранний граф з 11 вершинами, в якому всі грані трикутні — граф Голднера — Харарі[ru][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].

Спеціальні випадки

Багатогранний граф — граф простого багатогранника, якщо він є кубічним (в кожній вершині сходяться три ребра), і це граф симпліціального багатогранника, якщо він є максимальним планарним графом. Графи Халіна, утворені з планарних дерев шляхом додавання зовнішнього циклу, що проходить через всі листки дерева, утворюють інший важливий підклас багатогранних графів.

Примітки

  1. Günter M. Ziegler. Lectures on Polytopes. — 1995. — С. 103, Глава 4 "Steinitz' Theorem for 3-Polytopes". — ISBN 0-387-94365-X.
  2. Branko Grünbaum. Convex Polytopes. — Springer-Verlag, 2003. — Т. 221. — (Graduate Texts in Mathematics). — ISBN 978-0-387-40409-7.
  3. W. T. Tutte. How to draw a graph. — 1963. — Т. 13. — С. 743–767. — DOI:10.1112/plms/s3-13.1.743.
  4. Weisstein, Eric W. Herschel Graph(англ.) на сайті Wolfram MathWorld.
  5. Weisstein, Eric W. Goldner-Harary Graph(англ.) на сайті Wolfram MathWorld.
  6. Weisstein, Eric W. Shortness Exponent(англ.) на сайті Wolfram MathWorld.
  7. 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:10.1112/jlms/s1-37.1.152.
  8. A. J. W. Duijvestijn. The number of polyhedral (3-connected planar) graphs // Mathematics of Computation. — 1996. — Т. 65. — С. 1289–1293. — DOI:10.1090/S0025-5718-96-00749-1.
  9. послідовність A002840 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
  10. послідовність A000944 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

Посилання