Полиэдральный граф
Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
Содержание
Описание
Диаграмма Шлегеля выпуклого многогранника представляет его вершины и рёбра как точки и отрезки на евклидовой плоскости, образуя разбиение внешнего выпуклого многоугольника на более мелкие выпуклые многоугольники. Диаграмма не имеет самопересечений, так что любой полиэдральный граф является также планарным. Кроме того, по теорема Балинского[en], этот граф является вершинно 3-связным.
Согласно теореме Штейница[en] этих двух свойств достаточно, чтобы полностью описать полиэдральные графы — это в точности вершинно 3-связные планарные графы. Таким образом, если граф и планарен, и вершинно 3-связен, существует многогранник, вершины и рёбра которого образуют изоморфный исходному граф[1][2]. Если задан такой граф, представление его в виде разбиения выпуклого многоугольника на меньшие выпуклые многоугольники может быть найдено с помощью вложения Татта[en][3].
Гамильтоновость и показатель короткости
Тэйт высказал гипотезу[en], что любой кубический полиэдральный граф (то есть полиэдральный граф, в котором каждая вершина инцидентна в точности трём рёбрам) имеет гамильтонов цикл, но эта гипотеза была опровергнута Уильямом Таттом[en], построившим контрпример — полиэдральный негамильтонов граф (граф Татта). Если ослабить условие, что граф должен быть кубическим, появится много других меньших по размерам негамильтоновых полиэдральных графов, один из них, имеющий 11 вершин и 18 рёбер — граф Хершеля[4], существует также негамильтонов полиэдральный граф с 11 вершинами, в котором все грани треугольны — граф Голднера — Харари[en][5].
Строго говоря, существует константа <math>\alpha < 1</math> (показатель короткости[уточнить]) и бесконечное семейство полиэдральных графов, таких что длина самого длинного простого пути графа с <math>n</math> вершинами в семействе равна <math>O(n^\alpha)</math>[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].
Можно также перечислить[en] полиэдральные графы по числу их вершин, число таких графов равно:
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, …[10].
Специальные случаи
Полиэдральный граф — граф простого многогранника, если он является кубическим (в каждую вершину сходятся три ребра), и это граф симплициального многогранника, если он является максимальным планарным графом. Графы Халина, образованные из планарных деревьев путём добавления внешнего цикла, проходящего через все листья дерева, образуют другой важный подкласс полиэдральных графов.
Напишите отзыв о статье "Полиэдральный граф"
Примечания
- ↑ Günter M. Ziegler. Lectures on Polytopes. — 1995. — С. 103, Глава 4 "Steinitz' Theorem for 3-Polytopes". — ISBN 0-387-94365-X.
- ↑ Branko Grünbaum. Convex Polytopes. — Springer-Verlag, 2003. — Т. 221. — (Graduate Texts in Mathematics). — ISBN 978-0-387-40409-7.
- ↑ W. T. Tutte How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — DOI:10.1112/plms/s3-13.1.743.
- ↑ Weisstein, Eric W. [mathworld.wolfram.com/HerschelGraph.html Herschel Graph] (англ.) на сайте Wolfram MathWorld.
- ↑ Weisstein, Eric W. [mathworld.wolfram.com/Goldner-HararyGraph.html Goldner-Harary Graph] (англ.) на сайте Wolfram MathWorld.
- ↑ Weisstein, Eric W. [mathworld.wolfram.com/ShortnessExponent.html 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:10.1112/jlms/s1-37.1.152.
- ↑ 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.
- ↑ последовательность A002840 в OEIS
- ↑ последовательность A000944 в OEIS
Ссылки
- Weisstein, Eric W. [mathworld.wolfram.com/PolyhedralGraph.html Polyhedral Graph] (англ.) на сайте Wolfram MathWorld.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Полиэдральный граф
– Цел, Петров? – спрашивал один.– Задали, брат, жару. Теперь не сунутся, – говорил другой.
– Ничего не видать. Как они в своих то зажарили! Не видать; темь, братцы. Нет ли напиться?
Французы последний раз были отбиты. И опять, в совершенном мраке, орудия Тушина, как рамой окруженные гудевшею пехотой, двинулись куда то вперед.
В темноте как будто текла невидимая, мрачная река, всё в одном направлении, гудя шопотом, говором и звуками копыт и колес. В общем гуле из за всех других звуков яснее всех были стоны и голоса раненых во мраке ночи. Их стоны, казалось, наполняли собой весь этот мрак, окружавший войска. Их стоны и мрак этой ночи – это было одно и то же. Через несколько времени в движущейся толпе произошло волнение. Кто то проехал со свитой на белой лошади и что то сказал, проезжая. Что сказал? Куда теперь? Стоять, что ль? Благодарил, что ли? – послышались жадные расспросы со всех сторон, и вся движущаяся масса стала напирать сама на себя (видно, передние остановились), и пронесся слух, что велено остановиться. Все остановились, как шли, на середине грязной дороги.
Засветились огни, и слышнее стал говор. Капитан Тушин, распорядившись по роте, послал одного из солдат отыскивать перевязочный пункт или лекаря для юнкера и сел у огня, разложенного на дороге солдатами. Ростов перетащился тоже к огню. Лихорадочная дрожь от боли, холода и сырости трясла всё его тело. Сон непреодолимо клонил его, но он не мог заснуть от мучительной боли в нывшей и не находившей положения руке. Он то закрывал глаза, то взглядывал на огонь, казавшийся ему горячо красным, то на сутуловатую слабую фигуру Тушина, по турецки сидевшего подле него. Большие добрые и умные глаза Тушина с сочувствием и состраданием устремлялись на него. Он видел, что Тушин всею душой хотел и ничем не мог помочь ему.
Со всех сторон слышны были шаги и говор проходивших, проезжавших и кругом размещавшейся пехоты. Звуки голосов, шагов и переставляемых в грязи лошадиных копыт, ближний и дальний треск дров сливались в один колеблющийся гул.
Теперь уже не текла, как прежде, во мраке невидимая река, а будто после бури укладывалось и трепетало мрачное море. Ростов бессмысленно смотрел и слушал, что происходило перед ним и вокруг него. Пехотный солдат подошел к костру, присел на корточки, всунул руки в огонь и отвернул лицо.
– Ничего, ваше благородие? – сказал он, вопросительно обращаясь к Тушину. – Вот отбился от роты, ваше благородие; сам не знаю, где. Беда!
Вместе с солдатом подошел к костру пехотный офицер с подвязанной щекой и, обращаясь к Тушину, просил приказать подвинуть крошечку орудия, чтобы провезти повозку. За ротным командиром набежали на костер два солдата. Они отчаянно ругались и дрались, выдергивая друг у друга какой то сапог.
– Как же, ты поднял! Ишь, ловок, – кричал один хриплым голосом.
Потом подошел худой, бледный солдат с шеей, обвязанной окровавленною подверткой, и сердитым голосом требовал воды у артиллеристов.
– Что ж, умирать, что ли, как собаке? – говорил он.
Тушин велел дать ему воды. Потом подбежал веселый солдат, прося огоньку в пехоту.
– Огоньку горяченького в пехоту! Счастливо оставаться, землячки, благодарим за огонек, мы назад с процентой отдадим, – говорил он, унося куда то в темноту краснеющуюся головешку.
За этим солдатом четыре солдата, неся что то тяжелое на шинели, прошли мимо костра. Один из них споткнулся.
– Ишь, черти, на дороге дрова положили, – проворчал он.
– Кончился, что ж его носить? – сказал один из них.
– Ну, вас!
И они скрылись во мраке с своею ношей.
– Что? болит? – спросил Тушин шопотом у Ростова.
– Болит.
– Ваше благородие, к генералу. Здесь в избе стоят, – сказал фейерверкер, подходя к Тушину.
– Сейчас, голубчик.
Тушин встал и, застегивая шинель и оправляясь, отошел от костра…
Недалеко от костра артиллеристов, в приготовленной для него избе, сидел князь Багратион за обедом, разговаривая с некоторыми начальниками частей, собравшимися у него. Тут был старичок с полузакрытыми глазами, жадно обгладывавший баранью кость, и двадцатидвухлетний безупречный генерал, раскрасневшийся от рюмки водки и обеда, и штаб офицер с именным перстнем, и Жерков, беспокойно оглядывавший всех, и князь Андрей, бледный, с поджатыми губами и лихорадочно блестящими глазами.
