Граф Петерсена

Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.

Граф Петерсена
Назван в честь	Юлиус Петерсен
Вершин	10
Рёбер	15
Радиус	2
Диаметр	2
Обхват	5
Автоморфизмы	120 (S5)
Хроматическое число	3
Хроматический индекс	4
Род	1
Свойства	Кубический Сильно регулярный Дистанционно-транзитивный Снарк
Медиафайлы на Викискладе

Назван в честь Юлиуса Петерсена, построившего его в 1898 году как наименьший кубический граф без мостов, не имеющий рёберной раскраски в три цвета^[1]. При этом первое упоминание такого графа отмечено в статье Кемпе 1886 года^[2], в которой отмечено, что его вершины можно рассматривать как десять прямых конфигурации Дезарга, а рёбра представляют пары прямых, пересечение которых не принадлежит конфигурации.

Дональд Кнут отмечает граф как примечательный тем, что даёт контрпримеры ко многим «оптимистичным» высказываниям о графах в целом^[3].

Граф Петерсена появляется также в тропической геометрии: конус над графом Петерсена естественным образом идентифицируется модульным пространством пятиточечных рациональных тропических кривых.

Построение

Граф Петерсена как кнезеровский граф ${\displaystyle KG_{5,2}}$

Граф Петерсена является дополнением рёберного графа для ${\displaystyle K_{5}}$. Граф является также кнезеровским графом ${\displaystyle KG_{5,2}}$. Это означает, что граф имеет одну вершину для каждого 2-элементного подмножества 5-элементного множества, а две вершины связаны ребром тогда и только тогда, когда соответствующие 2-элементные подмножества не пересекаются. В качестве кнезеровского графа вида ${\displaystyle KG_{2n-1,n-1}}$ граф является нечётным графом.

Геометрически, граф Петерсена является графом, образованным вершинами и рёбрами полудодекаэдра, то есть додекаэдра с отождествлёнными противоположными вершинами, рёбрами и гранями.

Вложения

Граф Петерсена не является планарным. Любой непланарный граф имеет в качестве миноров либо полный граф ${\displaystyle K_{5}}$, либо полный двудольный граф ${\displaystyle K_{3,3}}$, но граф Петерсена имеет оба графа в качестве миноров. Минор ${\displaystyle K_{5}}$ можно получить путём стягивания рёбер совершенного паросочетания, например, пяти коротких рёбер на первом рисунке. Минор ${\displaystyle K_{3,3}}$ можно получить удалением одной вершины (например, центральной вершины 3-симметричного рисунка) и стягивания рёбер, инцидентных каждому соседу удалённой вершины.

Граф Петерсена имеет число пересечений 2 и является 1-планарным.

Общепринятый наиболее симметричный плоский рисунок графа Петерсена в виде пятиугольника внутри пятиугольника имеет пять пересечений. Однако это не самый оптимальный рисунок, минимизирующий число пересечений. Существует другой рисунок (показан справа) лишь с двумя пересечениями. Таким образом, граф Петерсена имеет число пересечений 2. Каждое ребро в этом рисунке пересекается не более одного раза, так что граф Петерсена является 1-планарным. На торе граф Петерсена может быть нарисован без пересечения рёбер. Таким образом, граф имеет ориентируемый род 1.

Граф Петерсена является графом единичных расстояний — его можно нарисовать на плоскости с рёбрами единичной длины.

Граф Петерсена может быть также нарисован (с пересечениями) на плоскости таким образом, что все рёбра имеют одинаковую длину. Таким образом, граф является графом единичных расстояний.

Простейшая неориентируемая поверхность^[англ.], в которую граф Петерсена можно вложить без пересечений, — это проективная плоскость. Это вложение, которое задаётся построением графа Петерсена как полудодекаэдра. Вложение в проективную плоскость можно также образовать из стандартного пятиугольного рисунка графа Петерсена путём помещения плёнки (разрезанной бутылки Кляйна) внутрь пятиугольной звезды в центре рисунка и направления рёбер звезды через эту плёнку. Полученный рисунок имеет шесть пятиугольных граней. Это построение образует правильную карту и показывает, что граф Петерсена имеет неориентируемый род 1.

Симметрии

Граф Петерсена является сильно регулярным (с сигнатурой srg(10,3,0,1)). Граф является также симметричным, что означает, что он является рёберно-транзитивным и вершинно-транзитивным. Более строго, граф является 3-транзитивным по дугам — любой ориентированный путь из трёх путей в графе Петерсена может быть переведён в любой другой такой путь симметрией графа^[4]. Граф является одним из 13 кубических дистанционно-регулярных графов.^[5]

Группой автоморфизмов графа Петерсена является симметрическая группа ${\displaystyle S_{5}}$. Действие ${\displaystyle S_{5}}$ на граф Петерсена следует из его построения в виде кнезеровского графа. Любой гомеоморфизм графа Петерсена на себя, не отождествляющий смежные вершины, является автоморфизмом. Как показано на иллюстрациях, рисунки графа Петерсена могут показать симметрии в пяти направлениях или в трёх направлениях, но невозможно нарисовать граф Петерсена на плоскости таким образом, чтобы рисунок показывал полную симметрию группы графа.

Несмотря на высокую симметрию, граф Петерсена не является графом Кэли, он является наименьшим вершинно-транзитивным графом, не являющемся графом Кэли.^[6]

Гамильтоновы пути и циклы

Граф Петерсена является гипогамильтоновым — удаление любой вершины, как, например, центральной вершины на рисунке, делает граф гамильтоновым. Рисунок с тремя симметриями предложил Кемпе (Kempe 1886).

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

Как конечный связный вершинно-транзитивный граф, не имеющий гамильтонова цикла, граф Петерсена является контрпримером варианта гипотезы Ловаса, но каноническая формулировка гипотезы спрашивает о гамильтоновом пути и для графа Петерсена эта гипотеза выполняется.

Известны только пять связных вершинно-транзитивных графов без гамильтоновых циклов — полный граф K₂, граф Петерсена, граф Коксетера и два графа, полученных из графов Петерсена и Коксетера путём замены каждой вершины треугольником^[7]. Если G является 2-связным, r-регулярным графом с максимум 3r + 1 вершинами, то G является гамильтоновым или G является графом Петерсена^[8].

Чтобы показать, что граф Петерсена не имеет гамильтонова цикла C, рассмотрим рёбра, соединяющие внутренний цикл из 5 вершин с внешним циклом. Если существует гамильтонов цикл, должно быть выбрано чётное число этих рёбер. Если выбрано только два ребра, их конечные вершины должны быть смежными в обоих циклах с 5 вершинами, что невозможно. Таким образом, должно быть выбрано 4 ребра. Предположим, что верхнее ребро не выбрано (все другие случаи аналогичны ввиду симметрии). Из 5 рёбер внешнего цикла два верхних ребра должны входить в гамильтонов цикл, так что два боковых ребра в цикл входить не должны, а тогда нижнее ребро должно входить в цикл. Два верхних ребра во внутреннем цикле должны быть выбраны, но тогда эти два ребра замыкают цикл, не являющийся полным, так что он не может быть частью гамильтонова цикла. Альтернативно, мы можем рассмотреть 3-регулярные графы с десятью вершинами, имеющими гамильтонов цикл, и показать, что ни один из этих графов не является графом Петерсена, путём нахождения цикла в каждом из них, более короткого, чем любой цикл графа Петерсена. Любой гамильтонов 3-регулярный граф с десятью вершинами состоит из цикла с десятью вершинами цикла C, плюс пять хорд. Если любая хорда соединяет две вершины вдоль C на расстоянии два или три друг от друга, то граф имеет 3-цикл или 4-цикл, а потому графом Петерсена быть не может. Если две хорды соединяют противоположные вершины цикла C на расстоянии четыре вдоль C, снова имеется 4-цикл. Остаётся только случай лестницы Мёбиуса, образованной соединением каждой пары противоположных сторон хордой, которая снова имеет 4-цикл. Поскольку обхват графа Петерсена равен пяти, он не может быть образован таким образом, а следовательно, не имеет гамильтонова цикла.

Раскраска

Раскраска рёбер графа Петерсена в 4 цвета

Раскраска вершин графа Петерсена в 3 цвета

Граф Петерсена имеет хроматическое число 3, это означает, что вершины графа могут быть раскрашены в три цвета, но не в два, таким образом, что никакое ребро не соединяет две вершины одного цвета. Граф имеет предписанную раскраску в 3 цвета согласно теореме Брукса для предписанных раскрасок. Граф Петерсена имеет хроматический индекс 4, то есть раскраска рёбер требует четырёх цветов. Иными словами, граф не является суммой трех 1-факторов, что показал ещё сам Петерсен^[9]. Для доказательства этого требуется проверить четыре случая, чтобы показать, что не существует раскраски рёбер в 3 цвета. Как связный кубический граф без мостов с хроматическим индексом четыре, граф Петерсена является снарком. Этот граф — наименьший возможный снарк. Он был единственным известным снарком в период 1898—1946 годов. Теорема о снарках, высказанная в форме гипотезы Таттом (доказана в 2001 году Робертсоном, Сандерсом, Сеймуром и Томасом^[10]), утверждает, что любой снарк имеет граф Петерсена в качестве минора.

Кроме того, граф имеет дробный хроматический индекс 3, что подтверждает утверждение, что разница между хроматическим индексом и дробным хроматическим индексом может быть равна 1. Давняя гипотеза Голдберга—Сеймура предполагает, что это наибольшая возможная разница.

Число Туэ (вариант хроматического индекса) графа Петерсена равно 5.

Граф Петерсена требует по меньшей мере трёх цветов в любой (возможно, несобственной) раскраске, которая нарушает все симметрии. То есть характерное число раскраски графа равно трём. За исключением полных графов, есть только кнезеровский граф, характерное число которого не равно двум^[11].

Другие свойства

Граф Петерсена:

• является 3-связным, а потому рёберно 3-связным и не имеющим мостов. См. Связный граф.
• имеет число независимости 4 и является 3-дольным. См. Задача о независимом множестве.
• является кубическим графом, имеет число доминирования 3, имеет совершенное паросочетание и 2-фактор.
• имеет 6 различных совершенных паросочетаний.
• является наименьшим кубическим графом с обхватом 5. (Это единственная ${\displaystyle (3,5)}$-клетка. Граф имеет только 10 вершин, поэтому он является единственным ${\displaystyle (3,5)}$-графом Мура.)^[12].
• имеет радиус 2 и диаметр 2. Это наибольший кубический граф с диаметром 2^[13]
• имеет спектр графа −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
• имеет 2000 остовных деревьев, больше чем любой кубический граф с 10 вершинами^[14]
• имеет хроматический многочлен ${\displaystyle t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right).}$ ^[15]
• имеет характеристический многочлен ${\displaystyle (t-1)^{5}(t+2)^{4}(t-3)}$, что делает его целым графом — графом, спектр которого полностью состоит из целых чисел.
• Между любыми двумя вершинами существует единственный путь длины не более двух.

Петерсеново семейство графов.

Гипотеза Петерсена о раскраске

Согласно Девосу, Нешетрилу и Распо «Цикл графа G — это множество C ${\displaystyle \subseteq }$ E(G), такое, что любая вершина графа (V(G),C) имеет чётную степень. Если G,H являются графами, мы определяем отображение φ: E(G) —> E(H) как непрерывное по циклам, если прообраз любого цикла в H является циклом в G. Франсуа Жагер (François Jaeger) сформулировал гипотезу, которая утверждает, что любой граф без мостов имеет непрерывное по циклам отображение в граф Петерсена. Жагер показал, что если гипотеза верна, то верна и гипотеза о двойном покрытии циклами длины 5 и гипотеза Бержа — Фалкерсона.»^[16].

Связанные графы

Обобщённый граф Петерсена G(n,k) образуется путём соединения вершин правильного n-угольника с соответствующими вершинами звёздчатого многоугольника с символом Шлефли {n/k}^[17][18]. Например, в этих обозначениях граф Петерсена имеет обозначение G(5,2) — его можно образовать соединением соответствующих вершин пятиугольника и пятиугольной звезды, при этом вершины звезды соединяются через одну. Обобщённые графы Петерсена также включает n-призмы G(n,1), граф Дюрера G(6,2), граф Мёбиуса — Кантора G(8,3), граф додекаэдра G(10,2), граф Дезарга G(10,3) и граф Науру G(12,5).

Петерсеново семейство графов состоит из семи графов, которые можно образовать из графа Петерсена путём нулевого и более числа применений преобразований Δ-Y или Y-Δ. Полный граф K₆ также входит в петерсеново семейство. Эти графы образуют запрещённые миноры для вложимых без зацеплений графов, графов, которые могут быть вложены в трёхмерное пространство таким образом, что никакие два цикла в графе не зацеплены^[19]

Граф Клебша состоит из копий графа Петерсена как порождённых подграфов — для каждой вершины v графа Клебша десять не являющихся соседями вершин v порождают копию графа Петерсена.

Примечания

1. The Petersen graph. Архивировано 8 июня 2011 года.
2. Kempe, 1886.
3. Knuth, 2011.
4. Babai, 1995, с. 1447–1540.
5. According to the Список Фостера.
6. Как указано, это допускает, что графы Кэли не обязательно связен. Некоторые источники требуют, чтобы графы Кэли были связными, что делает пустой граф с двумя вершинами является наименьшим вершинно-транзитивным графом, не являющимся графом Кэли. По определению, данному в этих источниках, граф Петерсена является наименьшим связным вершинно-транзитивным графом, не являющимся графом Кэли.
7. Royle, G. «Cubic Symmetric Graphs (The Foster Census).» Архивировано 20 июля 2008 года.
8. Holton, Sheehan, 1993, с. 32.
9. Харари, 2003, с. 113.
10. Pegg, 2002, с. 1084–1086.
11. Albertson, Boutin, 2007, с. R20.
12. Hoffman, Singleton, 1960, с. 497–504.
13. Это следует из факта, что граф является графом Мура, поскольку граф Мура является наибольшим возможным регулярным графом с такой степенью вершин и диаметром (Hoffman, Singleton 1960).
14. Jakobson, Rivin, 1999; Valdes, 1991. Кубические графы с 6 и 8 вершинами, на которых число остовных деревьев максимизируется, это лестницы Мёбиуса.
15. Biggs, 1993.
16. DeVos, Nešetřil, Raspaud, 2007, с. 109–138.
17. Coxeter, 1950.
18. Watkins, 1969.
19. Bailey, 1997, с. 187.

Литература

• Ф. Харари. Теория графов. — М.: УРСС, 2003. — ISBN 5-354-00301-6.
• О. Оре. Теория графов. — М.: УРСС, 2008. — ISBN 978-5-397-00044-4.
• Ed Pegg, Jr. Book Review: The Colossal Book of Mathematics (англ.) // Notices of the American Mathematical Society. — 2002. — Vol. 49, iss. 9. — doi:10.1109/TED.2002.1003756. — Bibcode: 2002ITED...49.1084A.
• Rosemary A. Bailey. Surveys in Combinatorics. — Cambridge University Press, 1997. — ISBN 978-0-521-59840-8.
• Matt DeVos, Jaroslav Nešetřil, André Raspaud. On edge-maps whose inverse preserves flows or tensions // Graph theory in Paris. — Basel: Birkhäuser, 2007. — С. 109—138. — (Trends Math.). — doi:10.1007/978-3-7643-7400-6_10.
• Norman Biggs. Algebraic Graph Theory. — 2nd. — Cambridge: Cambridge University Press, 1993. — ISBN 0-521-45897-8.
• László Babai. Automorphism groups, isomorphism, reconstruction // Handbook of Combinatorics / Ronald L. Graham, Martin Grötschel, László Lovász. — North-Holland, 1995. — Т. I. Архивная копия от 11 июня 2010 на Wayback Machine
• Alan J. Hoffman, Robert R. Singleton. Moore graphs with diameter 2 and 3 // IBM Journal of Research and Development. — 1960. — Т. 5, вып. 4. — С. 497—504. — doi:10.1147/rd.45.0497.
• Michael O. Albertson, Debra L. Boutin. Using determining sets to distinguish Kneser graphs // Electronic Journal of Combinatorics. — 2007. — Т. 14, вып. 1.
• Geoffrey Exoo, Frank Harary, Frank Harary. The crossing numbers of some generalized Petersen graphs // Mathematica Scandinavica. — 1981. — Т. 48. — С. 184—188.
• H. S. M. Coxeter. Self-dual configurations and regular graphs (англ.) // Bulletin of the American Mathematical Society. — 1950. — Vol. 56, iss. 5. — P. 413—455. — doi:10.1090/S0002-9904-1950-09407-5.
• D. A. Holton, J. Sheehan. The Petersen Graph. — Cambridge University Press, 1993. — ISBN 0-521-43594-3. — doi:10.2277/0521435943. Архивная копия от 8 февраля 2008 на Wayback Machine
• Dmitry Jakobson, Igor Rivin. On some extremal problems in graph theory. — 1999. — arXiv:math.CO/9907050.
• A. B. Kempe. A memoir on the theory of mathematical form // Philosophical Transactions of the Royal Society of London. — 1886. — Т. 177. — С. 1—70. — doi:10.1098/rstl.1886.0002.
• László Lovász. Combinatorial Problems and Exercises. — 2nd. — North-Holland, 1993. — ISBN 0-444-81504-X.
• Julius Petersen. Sur le théorème de Tait // L'Intermédiaire des Mathématiciens. — 1898. — Т. 5. — С. 225—227.
• A. J. Schwenk. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // Journal of Combinatorial Theory. — 1989. — Т. 47, вып. 1. — С. 53—59. — doi:10.1016/0095-8956(89)90064-6.
• L. Valdes. Extremal properties of spanning trees in cubic graphs // Congressus Numerantium. — 1991. — Т. 85. — С. 143—160.
• Mark E. Watkins. A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs // Journal of Combinatorial Theory. — 1969. — Т. 6, вып. 2. — С. 152—164. — doi:10.1016/S0021-9800(69)80116-X.
• Donald E. Knuth. A draft of section 7: Introduction to combinatorial searching // The Art of Computer Programming. — Т. 4, pre-fascicle 0A.
  • Donald E. Knuth. Combinatorial Algorithms, Part 1. — Upper Saddle River, New Jersey: Addison-Wesley, 2011. — ISBN 0-201-03804-8.
  • Дональд Э. Кнут. Глава 7: Комбинаторный поиск // Искусство программирования. — Москва, Санкт-Петербург, Киев: ООО «И.Д. Вильямс», 2013. — Т. 4, А / Комбинаторные алгоритмы, часть 1. — ISBN 978-5-8459-1744-7 ББК 32.973.26-18.2.75.

Ссылки

• Keller, Mitch. Kneser graphs Архивная копия от 5 мая 2018 на Wayback Machine PlanetMath
• Weisstein, Eric W. Petersen Graph (англ.) на сайте Wolfram MathWorld.
• Petersen Graph в Энциклопедии целочисленных последовательностей