Відкрити головне меню

Зміни

правопис
[[Файл:Dodecahedron_schlegel_diagram.png|міні|Багатогранний граф, утворений як {{нп|Діаграма Шлегеля|діаграма Шлегеля|ru|Диаграмма Шлегеля}} з {{нп|Правильний додекаедр|правильного додекаедра|ru|Правильный додекаэдр}}.]]
'''БагатограннийБагатогра́нний граф''', (або '''поліедральнийполіедра́льний граф''') — [[Граф (математика)|неорієнтований граф]], утворений з вершин і ребер [[Опуклий політоп|опуклого багатогранника]], або, в контексті теорії графів — [[K-вершинно-зв'язний граф|3-вершинно-зв'язний]] [[Планарний граф|планарний граф]].
 
== Опис ==
 
== Гамільтоновість і показник короткості ==
Тейт висловив {{нп|Гіпотеза Тейта (теорія графів)|гіпотезу|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>{{стаття