Многогранный граф

В геометрической теории графов , разделе математики , многогранный граф — это неориентированный граф, образованный из вершин и ребер многогранника выпуклого . В качестве альтернативы, чисто в терминах теории графов, многогранные графы представляют собой 3-связные плоские графы .

Характеристика [ править ]

Диаграмма Шлегеля выпуклого многогранника представляет его вершины и ребра в виде точек и отрезков евклидовой плоскости , образуя подразделение внешнего выпуклого многоугольника на меньшие выпуклые многоугольники ( выпуклый рисунок графика многогранника). Он не имеет пересечений, поэтому каждый многогранный граф также является плоским графом . Кроме того, по теореме Балинского это 3-связный граф .

Согласно теореме Стейница , этих двух теоретико-графовых свойств достаточно, чтобы полностью охарактеризовать многогранные графы: они в точности представляют собой 3-связные плоские графы. То есть, если граф одновременно плоский и 3-связный, существует многогранник, вершины и ребра которого образуют изоморфный граф. ^[1]^[2] Учитывая такой граф, его представление в виде подразделения выпуклого многоугольника на меньшие выпуклые многоугольники можно найти с помощью вложения Тутте . ^[3]

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

Тейт предположил , что каждый кубический многогранный граф (то есть многогранный граф, в котором каждая вершина инцидентна ровно трем ребрам) имеет гамильтонов цикл , но эта гипотеза была опровергнута контрпримером WT Tutte , многогранного, но не гамильтонова графа Тутта. . Если ослабить требование кубичности графа, появятся негамильтоновы многогранные графы гораздо меньшего размера. Граф с наименьшим количеством вершин и ребер — это граф Гершеля с 11 вершинами и 18 ребрами , ^[4] и существует также негамильтонов многогранный граф с 11 вершинами, в котором все грани являются треугольниками, граф Гольднера – Харари . ^[5]

Более строго, существует константа $\alpha <1$ ( показатель краткости ) и бесконечное семейство многогранных графов такое, что длина самого длинного простого пути $n$ -вершинный граф в семействе $O(n^{\alpha })$ . ^[6]^[7]

Комбинаторное перечисление [ править ]

Duijvestijn обеспечивает подсчет многогранных графов с числом ребер до 26; ^[8] Число этих графов с 6, 7, 8, ... ребрами равно

1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (последовательность A002840 в OEIS ).

Можно также нумеровать многогранные графы по количеству вершин: для графов с 4, 5, 6, ... вершинами количество многогранных графов равно

1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... (последовательность A000944 в OEIS ).

Особые случаи [ править ]

Графики Платоновых тел получили название Платоновых графов . Помимо того, что они обладают всеми остальными свойствами полиэдральных графов, они являются симметричными графами , и все они имеют гамильтоновы циклы . ^[9] Таких графиков пять:

Тетраэдрический граф – 4 вершины, 6 ребер.
Октаэдрический граф – 6 вершин, 12 ребер.
Кубический граф – 8 вершин, 12 ребер.
Икосаэдрический граф – 12 вершин, 30 ребер.
Додекаэдрический граф – 20 вершин, 30 ребер.

Многогранный граф — это график простого многогранника, если он кубический (каждая вершина имеет три ребра), и граф симплициального многогранника, если он является максимальным плоским графом . Например, тетраэдрические, кубические и додекаэдрические графы просты; тетраэдрические, октаэдрические и икосаэдрические графы являются симплициальными.

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

Ссылки [ править ]

^ Циглер, Гюнтер М. (1995), «Глава 4: Теорема Стейница для 3-многогранников», Лекции по многогранникам , стр. 103–126, ISBN 0-387-94365-Х
^ Грюнбаум, Бранко (2003), Выпуклые многогранники , Тексты для аспирантов по математике , том. 221 (2-е изд.), Springer-Verlag, ISBN 978-0-387-40409-7 .
^ Тутте, WT (1963), «Как нарисовать график», Труды Лондонского математического общества , 13 : 743–767, doi : 10.1112/plms/s3-13.1.743 , MR 0158387 .
^ Барнетт, Дэвид; Юкович, Эрнест (1970), «Гамильтоновы схемы на 3-многогранниках», Журнал комбинаторной теории , 9 (1): 54–59, doi : 10.1016/S0021-9800(70)80054-0
^ Гольднер, А.; Харари, Ф. (1975), «Замечание о наименьшем негамильтоновом максимальном плоском графе», Bull. Малазийская математика. Соц. , 6 (1): 41–42
^ Грюнбаум, Бранко ; Моцкин, Т.С. (1962), «Самые длинные простые пути в многогранных графах», Журнал Лондонского математического общества , s1-37 (1): 152–160, doi : 10.1112/jlms/s1-37.1.152
^ Оуэнс, Питер Дж. (1999), «Параметры краткости многогранных графов», Discrete Mathematics , 206 (1–3): 159–169, doi : 10.1016/S0012-365X(98)00402-6 , MR 1665396
^ Дуйвестейн, AJW (1996), «Количество многогранных (3-связных плоских) графов» (PDF) , Mathematics of Computation , 65 (215): 1289–1293, doi : 10.1090/S0025-5718-96-00749-1 .
^ Прочтите, Рональд К.; Уилсон, Робин Дж. (1998), «Глава 6: Специальные графики», Атлас графов , Oxford Science Publications, Oxford University Press, стр. 261, 266, ISBN 0-19-853289-Х , МР 1692656

Внешние ссылки [ править ]

Вайсштейн, Эрик В. , «Многогранный граф» , MathWorld

[1] Циглер, Гюнтер М. (1995), «Глава 4: Теорема Стейница для 3-многогранников», Лекции по многогранникам , стр. 103–126, ISBN 0-387-94365-Х

[grun-2] Грюнбаум, Бранко (2003), Выпуклые многогранники , Тексты для аспирантов по математике , том. 221 (2-е изд.), Springer-Verlag, ISBN 978-0-387-40409-7 .

[3] Тутте, WT (1963), «Как нарисовать график», Труды Лондонского математического общества , 13 : 743–767, doi : 10.1112/plms/s3-13.1.743 , MR 0158387 .

[4] Барнетт, Дэвид; Юкович, Эрнест (1970), «Гамильтоновы схемы на 3-многогранниках», Журнал комбинаторной теории , 9 (1): 54–59, doi : 10.1016/S0021-9800(70)80054-0

[5] Гольднер, А.; Харари, Ф. (1975), «Замечание о наименьшем негамильтоновом максимальном плоском графе», Bull. Малазийская математика. Соц. , 6 (1): 41–42

[6] Грюнбаум, Бранко ; Моцкин, Т.С. (1962), «Самые длинные простые пути в многогранных графах», Журнал Лондонского математического общества , s1-37 (1): 152–160, doi : 10.1112/jlms/s1-37.1.152

[7] Оуэнс, Питер Дж. (1999), «Параметры краткости многогранных графов», Discrete Mathematics , 206 (1–3): 159–169, doi : 10.1016/S0012-365X(98)00402-6 , MR 1665396

[8] Дуйвестейн, AJW (1996), «Количество многогранных (3-связных плоских) графов» (PDF) , Mathematics of Computation , 65 (215): 1289–1293, doi : 10.1090/S0025-5718-96-00749-1 .

[9] Прочтите, Рональд К.; Уилсон, Робин Дж. (1998), «Глава 6: Специальные графики», Атлас графов , Oxford Science Publications, Oxford University Press, стр. 261, 266, ISBN 0-19-853289-Х , МР 1692656

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]