Граф Петерсена: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
переименование категории |
Jumpow (обсуждение | вклад) Текст заменён переводом английской статьи "Petersen graph" |
||
| Строка 1: | Строка 1: | ||
{{Граф |
|||
{{викифицировать}} |
|||
|Название=Граф Петерсона |
|||
[[File:Petersen1 tiny.svg|thumb|right|Граф Петерсена]] |
|||
|Изображение=Petersen1 tiny.svg |
|||
[[File:Petersen2 tiny.svg|thumb|right|Другое представление графа Петерсена]] |
|||
| Назван в честь=[[ Петерсен, Юлиус|Юлиус Петерсен]] |
|||
'''Граф Петерсена''' — достаточно простой объект [[Теория графов|теории графов]] с интересными свойствами. Назван в честь [[Петерсен, Юлиус|Юлиуса Петерсена]], датского математика. |
|||
|Вершин=10 |
|||
|Рёбер=15 |
|||
|Автоморфизмы=120 (S<sub>5</sub>) |
|||
|Радиус=2 |
|||
|Диаметр=2 |
|||
|Обхват=5 |
|||
|Хроматическое число=3 |
|||
|Хроматический индекс=4 |
|||
|Род=1 |
|||
|Свойства=[[Кубический граф|Кубический]]<br/>[[Сильно регулярный граф|Сильно регулярный]]<br/>[[Дистанционно-транзитивный граф|Дистанционно-транзитивный]]<br/>[[ Снарк (теория графов)|Снарк]] |
|||
}} |
|||
'''Граф Петерсена''' — это [[неориентированный граф]] с 10 вершинами и 15 рёбрами. Это достаточно простой граф, используемый в качестве примера и контрпримера для многих задач теории графов. Граф назван в честь [[Петерсен, Юлиус|Юлиуса Петерсена]], датского математика, который построил его в 1898 как наименьший [[кубический граф]] [[Мост (теория графов)|без мостов]], не имеющий [[Рёберная раскраска|рёберной раскраски]] в три цвета <ref>{{статья|ссылка=http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html|заглавие=The Petersen graph|first=Andries E.|last=Brouwer|authorlink=Andries Brouwer}}</ref> |
|||
Хотя граф, как правило, приписывается Петерсону, фактически, он появился на 12 лет раньше в статье Кемпе {{sfn|Kempe|1886}}. Кемпе заметил, что вершины этого графа можно рассматривать как десять прямых [[Конфигурация Дезарга|конфигурации Дезарга]], а его рёбра представляют пары прямых, пересечение которых не принадлежит конфигурации. |
|||
== Общая информация == |
|||
Граф Петерсена является [[Орграф|неориентированным]] кубическим [[Граф_(математика)|графом]]. Его можно построить, взяв дополнение рёберного графа от полного 5-графа. Имеет 10 вершин и 15 рёбер. Сильно регулярен и рёберно регулярен, то есть, выбрав вершину или ребро можно отобразить граф на себя, переведя выбранный объект в любую вершину (ребро). Граф является [[Клетка (теория графов)|клеткой]] и [[Граф Мура|графом Мура]]. Его [[Автоморфизм|группа]] — '''S<sub>5</sub>'''. [[Теорема Дезарга|Конфигурация Дезарга]] в проективной геометрии соответствует дополнению графа Петерсена и соответственно имеет ту же группу '''S<sub>5</sub>'''. Граф является [[Кнезеровский граф|кнезеровским графом]] <math>KG_{5,2}</math>. |
|||
[[Кнут, Дональд Эрвин|Дональд Кнут]] утверждает, что граф Петерсена является «замечательной конфигурацией, дающей контрпримеры многим оптимистичным высказываниям о том, какие общие утверждения могут быть верны для графов в целом.» {{sfn|Knuth|2011}} |
|||
== Свойства == |
|||
* Не является гамильтоновым, в то же время, результат удаления вершины — [[гамильтонов граф]]. |
|||
Граф Петерсена появляется также в [[Тропическая геометрия|тропической геометрии]]. Конус над графом Петерсена естественным образом идентифицируется модульным пространством пятиточечных рациональных тропических кривых. |
|||
* [[Хроматическое число]] графа — 3. |
|||
* [[Рёберная раскраска|Хроматический класс]] (раскраска рёбер) — 4, иными словами, граф не является суммой трех [[Словарь терминов теории графов#Ф|1-факторов]], что показал ещё сам Петерсен.<ref name="Harary 113">Ф. Харари ''Теория графов'' стр. 113</ref> |
|||
== Построение== |
|||
* При изображении на плоскости имеет не менее двух самопересечений. |
|||
[[Файл:Kneser graph KG(5,2).svg|thumb|left|Граф Петерсена как кнезеровский граф <math>KG_{5,2}</math>]] |
|||
Граф Петерсена является [[Дополнение графа|дополнением]] [[Рёберный граф|рёберного графа]] для <math>K_5</math>. Граф является также [[Кнезеровский граф|кнезеровским графом]] <math>KG_{5,2}</math>. Это означает, что граф имеет одну вершину для каждого 2-элементного подмножества 5-элементного множества, а две вершины связаны ребром тогда и только тогда, когда соответствующие 2-элементные подмножества не пересекаются. В качестве кнезеровского графа вида <math>KG_{2n-1,n-1}</math> граф является [[Нечётный граф|нечётным графом]]. |
|||
Геометрически, граф Петерсена является графом, образованный вершинами и рёбрами {{не переведено 5|Полудодекаэдр|полудодекаэдра||hemi-dodecahedron}}, то есть [[додекаэдр]]а с отождествлёнными противоположными вершинами, рёбрами и гранями. |
|||
== Вложения == |
|||
Граф Петерсена не является [[Планарный граф|планарным]]. Любой непланарный граф имеет в качестве [[Минор графа|миноров]] либо [[полный граф]] <math>K_5</math>, либо [[полный двудольный граф]] <math>K_{3,3}</math>, но граф Петерсена имеет оба графа в качестве миноров. Минор <math>K_5</math> можно получить путём стягивания рёбер [[Паросочетание|совершенного паросочетания]], например, пяти коротких рёбер на первом рисунке. Минор <math>K_{3,3}</math> можно получить делением одной вершины (например, центральной вершину 3-симметричного рисунка) и стягивания рёбер инцидентных каждому соседу удалённой вершины. |
|||
[[Файл:Petersen graph, two crossings.svg|thumb|right| Граф Петерсена имеет [[Число пересечений (теория графов)|число пересечений]] 2 и является [[1-планарный граф|1-планарным]].]] |
|||
Общепринятый наиболее симметричный плоский рисунок графа Петерсена в виде пятиугольника внутри пятиугольника имеет пять пересечений. Однако, это не лучший рисунок, минимизирующий число пересечений. Существует другой рисунок (показан справа) лишь с двумя пересечениями. Таким образом, граф Петерсена имеет ''число пересечений'' 2. Каждое ребро в этом рисунке пересекается не более одного раза, так что граф Петерсена является [[1-планарный граф|1-планарным]]. На [[Тор (поверхность)|торе]] граф Петерсена может быть нарисован без пересечения рёбер. Таким образом, граф имеет [[Род поверхности|ориентируемый род]] 1. |
|||
[[Файл:Petersen graph, unit distance.svg|thumb|right|Граф Петерсена является [[Граф единичных расстояний|графом единичных расстояний]] — его можно нарисовать на плоскости с рёбрами единичной длины.]] |
|||
Граф Петерсена может быть также нарисовать (с пересечениями) на плоскости таким образом, что все рёбра имеют одинаковую длину. Таким образом, граф является [[Граф единичных расстояний|графом единичных расстояний]]. |
|||
Простейшая {{не переведено 5|Поверхность (математика)|неориентируемая поверхность||surface (mathematics)}}, в которую граф Петерсена можно вложить без пересечений, — это [[Проективная плоскость|проективная плоскость]]. Это вложение, которое задаётся построением графа Петерсена как {{не переведено 5|Полудодекаэдр|полудодекаэдра||hemi-dodecahedron}}. Вложение в проективную плоскость можно также образовать из стандартного пятиугольного рисунка графа Петерсена путём помещения {{не переведено 5|Плёнка (топология)|плёнки||cross-cap}} (разрезанной бутылки Кляйна) внутрь пятиугольной звезды в центре рисунка и направления рёбер звезды через эту плёнку. Полученный рисунок имеет шесть пятиугольных граней. Это построение образует {{не переведено 5|Правильная карта|правильную карту||Regular map (graph theory)}} и показывает, что граф Петерсена имеет [[Род поверхности|неориентируемый род]] 1. |
|||
== Симметрии == |
|||
Граф Петерсена является [[Сильно регулярный граф|сильно регулярным]] (с сигнатурой srg(10,3,0,1)). Граф является также [[symmetric graph|симметричным]], что означает, что он является [[Рёберно-транзитивный граф|рёберно-транзитивным]] и [[Вершинно-транзитивный граф|вершинно-транзитивным]]. Более строго, граф является 3-транзитивным по дугам — любой ориентированный путь из трёх путей в графе Петерсена может быть переведён в любой другой такой путь симметрией графа {{sfn|Babai|1995|с=1447–1540}}. |
|||
Граф является одним из 13 кубических [[Дистанционно-регулярный граф|дистанционно-регулярных графов]] <ref>According to the [[Список Фостера|Список Фостера]].</ref> |
|||
[[Автоморфизм графа|Группой автоморфизмов]] графа Петерсена является [[симметрическая группа]] <math>S_5</math>. Действие <math>S_5</math> на граф Петерсена следует из его построения в виде [[Кнезеровский граф|кнезеровского графа]]. Любой {{не переведено 5|Гомоморфизм графов|гомеоморфизм||graph homomorphism}} графа Петерсена на себя, не отождествляющий смежные вершины, является автоморфизмом. Как показано на иллюстрациях, рисунки графа Петерсена могут показать симметрии в пяти направлениях или в трёх направлениях, но невозможно нарисовать граф Петерсена на плоскости таким образом, чтобы рисунок показывал полную симметрию группы графа. |
|||
Не смотря на высокую симметрию, граф Петерсена не является [[Граф Кэли|графом Кэли]], он является наименьшим вершинно-транзитивным графом, не являющемся графом Кэли <ref>Как указано, это допускает, что графы Кэли не обязательно связен. Некоторые источники требуют, чтобы графы Кэли были связными, что делает {{не переведено 5|пустой граф|||empty graph}} с двумя вершинами является наименьшим вершинно-транзитивным графом, не являющимся графом Кэли. По определению, данному в этих источниках, граф Петерсена является наименьшим связным вершинно-транзитивным графом, не являющимся графом Кэли.</ref> |
|||
== Гамильтоновы пути и циклы == |
|||
[[Файл:Petersen2 tiny.svg|thumb|right|Граф Петерсена является гипогамильтоновым — удаление любой вершины, как, например, центральной вершины на рисунке, делает граф гамильтоновым. Рисунок с тремя симметриями предложил Кемпе {{harv|Kempe|1886}}.]] |
|||
Граф Петерсена имеет [[Гамильтонов граф|гамильтонов путь]], но не [[Гамильтонов граф|гамильтонов цикл]]. Граф является наименьшим кубическим графом без моста, не имеющим гамильтонова цикла. Граф является [[Гипогамильтонов граф|гипогамильтоновым]], что означает, что хотя он не имеет гамильтонова цикла, удаление любой вершины делает его гамильтоновым, и это наименьший гипогамильтонов граф. |
|||
Как конечный связный вершинно-транзитивный граф, не имеющий гамильтонова цикла, граф Петерсена является контрпримером варианта [[Гипотеза Ловаса о гамильтоновом цикле|гипотезы Ловаша]], но каноническая формулировка гипотезы спрашивает о гамильтоновом пути и для графа Петерсена эта гипотеза выполняется. |
|||
Известны только пять связных вершинно-транзитивных графов без гамильтоновых циклов — [[полный граф]] ''K''<sub>2</sub>, граф Петерсена, [[граф Коксетера]] и два графа, полученных из графов Петерсена и Коксетера путём замены каждой вершины треугольником <ref>Royle, G. [http://www.cs.uwa.edu.au/~gordon/remote/foster/#census "Cubic Symmetric Graphs (The Foster Census)."]</ref>. Если ''G'' является 2-связным, ''r''-регулярным графом с максимум 3''r'' + 1 вершинами, то ''G'' является гамильтоновым или ''G'' является графом Петерсена {{sfn|Holton, Sheehan|1993|с=32}}. |
|||
Чтобы показать, что граф Петерсена не имеет гамильтонова цикла ''C'', рассмотрим рёбра, соединяющие внутренний цикл из 5 вершин с внешним циклом. Если существует гамильтонов цикл, должно быть выбрано чётное число этих рёбер. Если выбрано только два ребра, их конечные вершины должны быть смежными в одном из циклов с 5 вершинами, что невозможно. Таким образом, должно быть выбрано 4 ребра. Предположим, что верхнее ребро не выбрано (все другие случаи аналогичны ввиду симметрии). Из 5 рёбер внешнего цикла два верхних ребра должны входить в гамильтонов цикл, так что два боковых ребра в цикл входить не должны, а тогда нижнее ребро должно входить в цикл. Два верхних ребра во внутреннем цикле должны быть выбраны, но тогда эти два ребра замыкают цикл, не являющийся полным, так что он не может быть частью гамильтонова цикла. Альтернативно, мы можем рассмотреть [[Регулярный граф|3-регулярные графы]] с десятью вершинами, имеющими гамильтонов цикл, и показать, что ни один из этих графов не является графом Петерсена, путём нахождения цикла в каждом из них, более короткого, чем любой цикл графа Петерсена. Любой гамильтонов 3-регулярный граф с десятью вершинами состоит из цикла с десятью вершинами цикла ''C'', плюс пять хорд. Если любая хорда соединяет две вершины вдоль ''C'' на расстоянии два или три друг от друга, то граф имеет 3-цикл или 4-цикл, а потому графом Петерсена быть не может. Если две хорды соединяют противоположные вершины цикла ''C'' на расстоянии четыре вдоль ''C'', снова имеется 4-цикл. Остаётся только случай [[Лестница Мёбиуса|лестницы Мёбиуса]] , образованной соединением каждой пары противоположных сторон хордой, которая снова имеет 4-цикл. Поскольку обхват графа Петерсена равен пяти, он не может быть образован таким образом, а следовательно, не имеет гамильтонова цикла. |
|||
== Раскраска == |
|||
[[Файл:PetersenBarveniHran.svg|thumb|left|Раскраска рёбер графа Петерсена в 4 цвета]] |
|||
[[Файл:Petersen graph 3-coloring.svg|thumb|right|Раскраска вершин графа Петерсена в 3 цвета]] |
|||
Граф Петерсена имеет [[Раскраска графов|хроматическое число]] 3, что означает, вершины графа могут быть [[Раскраска графов|раскрашены]] в три цвета, но не в два, таким образом, что никакое ребро не соединяет две вершины одного цвета. Граф имеет {{не переведено 5|Предписанная раскраска|предписанную раскраску||list colouring}} в 3 цвета согласно теореме Брукса для предписанных раскрасок. |
|||
Граф Петерсена имеет [[Рёберная раскраска|хроматический индекс]] 4, т.е. раскраска рёбер требует четырёх цветов. Иными словами, граф не является суммой трех [[Словарь терминов теории графов#Ф|1-факторов]], что показал ещё сам Петерсен {{sfn|Харари|2003|с=113}}. Доказательство этого требует проверки четырёх случаев, чтобы показать, что не существует раскраска рёбер в 3 цвета. Как связный кубический граф без мостов с хроматическим индексом четыре, граф Петерсена является [[Снарк (теория графов)|снарком]]. Это наименьший возможный снарк и был единственным известным снарком с 1898 по 1946. [[Снарк (теория графов)|Теорема о снарках]], высказанная в виде гипотезы [[Тат, Уильям Томас|Татом]] и доказательство которой было объявлено в 2001 Робертсоном, Сандерсом, Сеймуром и Томасом {{sfn|Pegg|2002|с=1084–1086}}, утверждает, что любой снарк имеет граф Петерсена в качестве [[Минор графа|минора]]. |
|||
Кроме того, граф имеет [[Дробная раскраска|дробный хроматический индекс]] 3, что подтверждает, что разница между хроматическим индексом и дробным хроматическим индексом может быть равна 1. Давняя гипотеза Голдберга — Сеймура предполагает, что это наибольшая возможная разница. |
|||
{{не переведено 5|Число Туэ|||Thue number}} (вариант хроматического индекса) графа Петерсена равно 5. |
|||
Граф Петерсена требует по меньшей мере трёх цветов в любой (возможно, несобственной) раскраске, которая нарушает все симметрии. То есть, {{не переведено 5|характерное число раскраски|||distinguishing number}} графа равно трём. За исключением полных графов, есть только кнезеровский граф, характерное число которого не равно двум {{sfn|Albertson, Boutin|2007|с=R20}}. |
|||
== Другие свойства == |
|||
Граф Петерсена: |
|||
* является 3-связным, а потому рёберно 3-связным и не имеющим мостов. См. [[Связный граф]]. |
|||
* имеет число независимости 4 и является 3-дольным. См. [[Задача о независимом множестве]]. |
|||
* является [[Кубический граф|кубическим графом]], имеет [[Доминирующее множество|число доминирования]] 3, имеет [[Паросочетание|совершенное паросочетание]] и [[Факторизация графа|2-фактор]]. |
|||
* имеет 6 различных совершенных паросочетаний. |
|||
* является наименьшим кубическим графом с [[Обхват (теория графов)|обхватом]] 5. (Это единственная <math>(3,5)</math>-[[ Клетка (теория графов)|клетка]]. Фактически, поскольку граф имеет только 10 вершин, он является единственным <math>(3,5)</math>-[[Граф Мура|графом Мура]].) {{sfn|Hoffman, Singleton|1960|с=497–504}}. |
|||
* имеет [[Расстояние (теория графов)|радиус]] 2 и [[Расстояние (теория графов)|диаметр]] 2. Это наибольший кубический граф с диаметром 2 <ref>Это следует из факта, что граф является графом Мура, поскольку граф Мура является наибольшим возможным регулярным графом с такой степенью вершин и диаметром {{harv|Hoffman|Singleton|1960}}.</ref> |
|||
* имеет [[Спектральная теория графов|спектр графа]] −2, −2, −2, −2, 1, 1, 1, 1, 1, 3. |
|||
* имеет 2000 [[Остовное дерево|остовных деревьев]], больше чем любой кубический граф с 10 вершинами <ref>{{harvnb|Jakobson, Rivin|1999}}; {{harvnb|Valdes|1991}}. Кубические графы с 6 и 8 вершинами, на которых число остовных деревьев максимизируется, это [[Лестница Мёбиуса|лестницы Мёбиуса]].</ref> |
|||
* имеет {{не переведено 5|хроматический многочлен|||chromatic polynomial}} <math>t(t-1)(t-2)\left(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352\right).</math> {{sfn|Biggs|1993}} |
|||
* имеет [[Характеристический многочлен матрицы|характеристический многочлен]] <math>(t-1)^5(t+2)^4(t-3)</math>, что делает его {{не переведено 5|Целый граф|целым графом||integral graph}} — графом, [[Спектральная теория графов|спектр]] которого полностью состоит из целых чисел. |
|||
* Между любыми двумя вершинами существует единственный путь длины не более двух. |
* Между любыми двумя вершинами существует единственный путь длины не более двух. |
||
== Гипотеза Петерсена о раскраске == |
|||
== См. также == |
|||
Согласно Девосу, Нешетрилу и Распауду «''Цикл'' графа G — это множество C <math>\subseteq</math> E(G), такое что любая вершина графа (V(G),C) имеет чётную степень. Если G,H являются графами, мы определяем отображение φ: E(G) —> E(H) как ''непрерывное по циклам'', если прообраз любого цикла в H является циклом в G. Обворожительная гипотеза Иегера утверждает, что любой граф без мостов имеет непрерывное по циклам отображение в граф Петерсена. Йегер показал, что если гипотеза верна, то верна и гипотеза о [[Двойное покрытие циклами|двойном покрытии циклами длины 5]] и гипотеза Бержа — Фулкерсона.» |
|||
*[[Планарный граф]] |
|||
{{sfn|DeVos, Nešetřil, Raspaud|2007|с=109–138}}. |
|||
==Связанные графы == |
|||
== Примечания == |
|||
[[Файл:Petersen family.svg|thumb|[[Петерсеново семейство графов]].]] |
|||
{{примечания}} |
|||
[[Обобщённый граф Петерсена]] ''G''(''n'',''k'') образуется путём соединения вершин [[Правильный многоугольник|правильного ''n''-угольника]] с соответствующими вершинами [[Звёздчатый многоугольник|звёздчатого многоугольника]] с [[Символ Шлефли|символом Шлефли]] {''n''/''k''} {{sfn|Coxeter|1950}}{{sfn|Watkins|1969}}. Например, в этих обозначениях граф Петерсена граф имеет обозначение ''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''<sub>6</sub> также входит в петерсеново семейство. Эти графы образуют [[Характеризация запрещёнными графами|запрещённые миноры]] для [[Незацепленное вложение графа|вложимых без зацеплений графов]], графов, которые могут быть вложены в трёхмерное пространство таким образом, что никакие два цикла в графе не [[Зацепление (теория узлов)|зацеплены]] {{sfn|Bailey|1997|с=187}} |
|||
== Литература == |
|||
* Ф. Харари ''Теория графов''. — {{М}}: [[УРСС]], — 2003. — 300 с. — ISBN 5-354-00301-6. |
|||
* [[Оре, Ойстин|О. Оре]] ''Теория графов''. — {{М}}: [[УРСС]], — 2008. — 352 с. — ISBN 978-5-397-00044-4. |
|||
[[Граф Клебша]] состоит из копий графа Петерсена как [[Порождённый подграф|порождённых подграфов]] — для каждой вершины ''v'' графа Клебша десять не являющихся соседями вершин ''v'' порождают копию графа Петерсена. |
|||
{{math-stub}} |
|||
{{clear}} |
|||
==Примечания== |
|||
{{примечания|2}} |
|||
==Литература== |
|||
{{refbegin|colwidth=30em}} |
|||
* {{книга |
|||
|автор=Ф. Харари |
|||
|ref=Харари |
|||
|заглавие=Теория графов |
|||
|место=М. |
|||
|издательство=[[УРСС]] |
|||
|год=2003 |
|||
|ISBN=5-354-00301-6 |
|||
}} |
|||
* {{книга |
|||
|автор=[[Оре, Ойстин|О. Оре]] |
|||
|ref=Оре |
|||
|заглавие=Теория графов |
|||
|место=М. |
|||
|издательство=[[УРСС]] |
|||
|год=2008 |
|||
|ISBN=978-5-397-00044-4 |
|||
}} |
|||
*{{статья |
|||
|автор=Ed Pegg, Jr. |
|||
|ref=Pegg |
|||
|заглавие=Book Review: The Colossal Book of Mathematics |
|||
|издание=Notices of the American Mathematical Society |
|||
|том=49 |
|||
|выпуск=9 |
|||
|год=2002 |
|||
|ссылка=http://www.ams.org/notices/200209/rev-pegg.pdf |
|||
|doi=10.1109/TED.2002.1003756 |
|||
|bibcode=2002ITED...49.1084A |
|||
}} |
|||
*{{книга |
|||
|заглавие=Surveys in Combinatorics |
|||
|ref=Bailey |
|||
|автор=Rosemary A. Bailey |
|||
|издательство=Cambridge University Press |
|||
|год=1997 |
|||
|isbn=978-0-521-59840-8 |
|||
}} |
|||
*{{книга |
|||
|автор=Matt DeVos, Jaroslav Nešetřil, André Raspaud |
|||
|ref=DeVos, Nešetřil, Raspaud |
|||
|часть=On edge-maps whose inverse preserves flows or tensions |
|||
|doi=10.1007/978-3-7643-7400-6_10 |
|||
|место=Basel |
|||
|mr=2279171 |
|||
|страницы=109–138 |
|||
|издательство=Birkhäuser |
|||
|серия=Trends Math. |
|||
|заглавие=Graph theory in Paris |
|||
|год=2007 |
|||
}} |
|||
*{{книга |
|||
|автор=Norman Biggs |
|||
|ref=Biggs |
|||
|заглавие=Algebraic Graph Theory |
|||
|издание=2nd |
|||
|место=Cambridge |
|||
|издательство=Cambridge University Press |
|||
|год=1993 |
|||
|isbn=0-521-45897-8 |
|||
}} |
|||
*{{книга |
|||
|автор=László Babai |
|||
|ref=Babai |
|||
|часть=Automorphism groups, isomorphism, reconstruction |
|||
|id=Corollary 1.8 |
|||
|заглавие=Handbook of Combinatorics |
|||
|ссылка=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |
|||
|ответственный=Ronald L. Graham, Martin Grötschel, László Lovász |
|||
|том=I |
|||
|издательство=North-Holland |
|||
|год=1995 |
|||
}} |
|||
*{{статья |
|||
|ref=Hoffman, Singleton |
|||
|автор=Alan J. Hoffman, Robert R. Singleton |
|||
|заглавие=Moore graphs with diameter 2 and 3 |
|||
|издание=IBM Journal of Research and Development |
|||
|том=5 |
|||
|выпуск=4 |
|||
|год=1960 |
|||
|страницы=497–504 |
|||
|ссылка=http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf |
|||
|mr=0140437 |
|||
|doi=10.1147/rd.45.0497 |
|||
}} |
|||
*{{статья |
|||
|автор=Michael O. Albertson, Debra L. Boutin |
|||
|ref=Albertson, Boutin |
|||
|выпуск=1 |
|||
|издание=Electronic Journal of Combinatorics |
|||
|mr=2285824 |
|||
|page=R20 |
|||
|заглавие=Using determining sets to distinguish Kneser graphs |
|||
|ссылка=http://www.combinatorics.org/Volume_14/Abstracts/v14i1r20.html |
|||
|том=14 |
|||
|год=2007 |
|||
}} |
|||
* {{статья |
|||
|автор=Geoffrey Exoo, Frank Harary, Frank Harary |
|||
|ref=Exoo, Harary, Harary |
|||
|заглавие=The crossing numbers of some generalized Petersen graphs |
|||
|издание=Mathematica Scandinavica |
|||
|том=48 |
|||
|год=1981 |
|||
|страницы=184–188 |
|||
}} |
|||
* {{статья |
|||
|ref=Coxeter |
|||
|автор=H. S. M. Coxeter |
|||
|заглавие=Self-dual configurations and regular graphs |
|||
|издание=[[Bulletin of the American Mathematical Society]] |
|||
|том=56 |
|||
|год=1950 |
|||
|страницы=413–455 |
|||
|doi=10.1090/S0002-9904-1950-09407-5 |
|||
|выпуск=5 |
|||
}} |
|||
* {{книга |
|||
|автор=D. A. Holton, J. Sheehan |
|||
|ref=Holton, Sheehan |
|||
|ссылка=http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521435943 |
|||
|заглавие=The Petersen Graph |
|||
|издательство=[[Cambridge University Press]] |
|||
|год=1993 |
|||
|isbn=0-521-43594-3 |
|||
|doi=10.2277/0521435943 |
|||
}} |
|||
* {{статья |
|||
|автор= Dmitry Jakobson, Igor Rivin |
|||
|ref=Jakobson, Rivin |
|||
|заглавие=On some extremal problems in graph theory |
|||
|год=1999 |
|||
|arxiv= math.CO/9907050 |
|||
}} |
|||
* {{статья |
|||
|автор=A. B. Kempe |
|||
|ref=Kempe |
|||
|заглавие=A memoir on the theory of mathematical form |
|||
|издание=Philosophical Transactions of the Royal Society of London |
|||
|том=177 |
|||
|страницы=1–70 |
|||
|год=1886 |
|||
|doi=10.1098/rstl.1886.0002 |
|||
}} |
|||
* {{книга |
|||
|автор=[[Ловас, Ласло|László Lovász]] |
|||
|ref=Lovász |
|||
|заглавие=Combinatorial Problems and Exercises |
|||
|издание=2nd |
|||
|издательство=North-Holland |
|||
|год=1993 |
|||
|isbn= 0-444-81504-X |
|||
}} |
|||
* {{статья |
|||
|автор=Julius Petersen |
|||
|ref=Petersen |
|||
|заглавие=Sur le théorème de Tait |
|||
|издание=L'Intermédiaire des Mathématiciens |
|||
|том=5 |
|||
|год=1898 |
|||
|страницы=225–227 |
|||
}} |
|||
* {{статья |
|||
|ref=Schwenk |
|||
|автор=A. J. Schwenk |
|||
|заглавие=Enumeration of Hamiltonian cycles in certain generalized Petersen graphs |
|||
|год=1989 |
|||
|страницы=53–59 |
|||
|издание= [[Journal of Combinatorial Theory]]|series=Series B |
|||
|том=47 |
|||
|выпуск=1 |
|||
|doi=10.1016/0095-8956(89)90064-6 |
|||
}} |
|||
* {{статья |
|||
|автор= L. Valdes |
|||
|ref=Valdes |
|||
|заглавие= Extremal properties of spanning trees in cubic graphs |
|||
|издание=Congressus Numerantium |
|||
|год=1991 |
|||
|том=85 |
|||
|страницы=143–160 |
|||
}} |
|||
* {{статья |
|||
|автор=Mark E. Watkins |
|||
|ref=Watkins |
|||
|заглавие= A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs |
|||
|издание=[[Journal of Combinatorial Theory]] |
|||
|год=1969 |
|||
|том=6 |
|||
|страницы=152–164 |
|||
|doi=10.1016/S0021-9800(69)80116-X |
|||
|выпуск=2 |
|||
}} |
|||
*{{книга |
|||
|автор=[[ Кнут, Дональд Эрвин|Donald E. Knuth]] |
|||
|заглавие=[[Искусство программирования|The Art of Computer Programming]] |
|||
|том=4, pre-fascicle 0A |
|||
|часть=A draft of section 7: Introduction to combinatorial searching |
|||
}} |
|||
**{{книга |
|||
|автор=[[Кнут, Дональд Эрвин|Donald E. Knuth]] |
|||
|ref=Knuth |
|||
|заглавие=Combinatorial Algorithms, Part 1 |
|||
|место=Upper Saddle River, New Jersey |
|||
|издательство=Addison-Wesley |
|||
|год=2011 |
|||
|ISBN=0-201-03804-8 |
|||
}} |
|||
**{{книга |
|||
|автор=[[Кнут, Дональд Эрвин|Дональд Э. Кнут]] |
|||
|ref= Кнут |
|||
|заглавие=Искусство программирования |
|||
|место=Москва, Санк-Петербург, Киев |
|||
|издательство=ООО «И.Д. Вильямс» |
|||
|год=2013 |
|||
|ISBN=978-5-8459-1744-7 ББК 32.973.26-18.2.75 |
|||
|часть=Глава 7: Комбинаторный поиск |
|||
|том=4, А / Комбинаторные алгоритмы, часть 1 |
|||
}} |
|||
{{refend}} |
|||
==Ссылки== |
|||
* Keller, Mitch. [http://planetmath.org/?op=getobj&from=objects&id=5732 Kneser graphs] [[PlanetMath]] |
|||
* {{MathWorld|urlname=PetersenGraph|title=Petersen Graph}} |
|||
* [http://oeis.org/search?q=Petersen+Graph&sort=&language=english&go=Search Petersen Graph] в [[Энциклопедия целочисленных последовательностей|Энциклопедии целочисленных последовательностей]] |
|||
[[Категория:Теория графов]] |
|||
[[Категория:Регулярные графы]] |
|||
[[Категория:Графы, имеющие собственные названия]] |
[[Категория:Графы, имеющие собственные названия]] |
||
[[Категория:Регулярные графы]] |
|||
{{rq|checktranslate|style|grammar}} |
|||
Версия от 11:47, 4 мая 2017
| Граф Петерсона | |
|---|---|
 | |
| Назван в честь | Юлиус Петерсен |
| Вершин | 10 |
| Рёбер | 15 |
| Радиус | 2 |
| Диаметр | 2 |
| Обхват | 5 |
| Автоморфизмы | 120 (S5) |
| Хроматическое число | 3 |
| Хроматический индекс | 4 |
| Род | 1 |
| Свойства |
Кубический Сильно регулярный Дистанционно-транзитивный Снарк |
 Медиафайлы на Викискладе | |
Граф Петерсена — это неориентированный граф с 10 вершинами и 15 рёбрами. Это достаточно простой граф, используемый в качестве примера и контрпримера для многих задач теории графов. Граф назван в честь Юлиуса Петерсена, датского математика, который построил его в 1898 как наименьший кубический граф без мостов, не имеющий рёберной раскраски в три цвета [1]
Хотя граф, как правило, приписывается Петерсону, фактически, он появился на 12 лет раньше в статье Кемпе [2]. Кемпе заметил, что вершины этого графа можно рассматривать как десять прямых конфигурации Дезарга, а его рёбра представляют пары прямых, пересечение которых не принадлежит конфигурации.
Дональд Кнут утверждает, что граф Петерсена является «замечательной конфигурацией, дающей контрпримеры многим оптимистичным высказываниям о том, какие общие утверждения могут быть верны для графов в целом.» [3]
Граф Петерсена появляется также в тропической геометрии. Конус над графом Петерсена естественным образом идентифицируется модульным пространством пятиточечных рациональных тропических кривых.
Построение
.svg)
Граф Петерсена является дополнением рёберного графа для . Граф является также кнезеровским графом . Это означает, что граф имеет одну вершину для каждого 2-элементного подмножества 5-элементного множества, а две вершины связаны ребром тогда и только тогда, когда соответствующие 2-элементные подмножества не пересекаются. В качестве кнезеровского графа вида граф является нечётным графом.
Геометрически, граф Петерсена является графом, образованный вершинами и рёбрами полудодекаэдра?!, то есть додекаэдра с отождествлёнными противоположными вершинами, рёбрами и гранями.
Вложения
Граф Петерсена не является планарным. Любой непланарный граф имеет в качестве миноров либо полный граф , либо полный двудольный граф , но граф Петерсена имеет оба графа в качестве миноров. Минор можно получить путём стягивания рёбер совершенного паросочетания, например, пяти коротких рёбер на первом рисунке. Минор можно получить делением одной вершины (например, центральной вершину 3-симметричного рисунка) и стягивания рёбер инцидентных каждому соседу удалённой вершины.
Общепринятый наиболее симметричный плоский рисунок графа Петерсена в виде пятиугольника внутри пятиугольника имеет пять пересечений. Однако, это не лучший рисунок, минимизирующий число пересечений. Существует другой рисунок (показан справа) лишь с двумя пересечениями. Таким образом, граф Петерсена имеет число пересечений 2. Каждое ребро в этом рисунке пересекается не более одного раза, так что граф Петерсена является 1-планарным. На торе граф Петерсена может быть нарисован без пересечения рёбер. Таким образом, граф имеет ориентируемый род 1.
Граф Петерсена может быть также нарисовать (с пересечениями) на плоскости таким образом, что все рёбра имеют одинаковую длину. Таким образом, граф является графом единичных расстояний.
Простейшая неориентируемая поверхность[англ.], в которую граф Петерсена можно вложить без пересечений, — это проективная плоскость. Это вложение, которое задаётся построением графа Петерсена как полудодекаэдра?!. Вложение в проективную плоскость можно также образовать из стандартного пятиугольного рисунка графа Петерсена путём помещения плёнки[англ.] (разрезанной бутылки Кляйна) внутрь пятиугольной звезды в центре рисунка и направления рёбер звезды через эту плёнку. Полученный рисунок имеет шесть пятиугольных граней. Это построение образует правильную карту[англ.] и показывает, что граф Петерсена имеет неориентируемый род 1.
Симметрии
Граф Петерсена является сильно регулярным (с сигнатурой srg(10,3,0,1)). Граф является также симметричным, что означает, что он является рёберно-транзитивным и вершинно-транзитивным. Более строго, граф является 3-транзитивным по дугам — любой ориентированный путь из трёх путей в графе Петерсена может быть переведён в любой другой такой путь симметрией графа [4]. Граф является одним из 13 кубических дистанционно-регулярных графов [5]
Группой автоморфизмов графа Петерсена является симметрическая группа . Действие на граф Петерсена следует из его построения в виде кнезеровского графа. Любой гомеоморфизм?! графа Петерсена на себя, не отождествляющий смежные вершины, является автоморфизмом. Как показано на иллюстрациях, рисунки графа Петерсена могут показать симметрии в пяти направлениях или в трёх направлениях, но невозможно нарисовать граф Петерсена на плоскости таким образом, чтобы рисунок показывал полную симметрию группы графа.
Не смотря на высокую симметрию, граф Петерсена не является графом Кэли, он является наименьшим вершинно-транзитивным графом, не являющемся графом Кэли [6]
Гамильтоновы пути и циклы
Граф Петерсена имеет гамильтонов путь, но не гамильтонов цикл. Граф является наименьшим кубическим графом без моста, не имеющим гамильтонова цикла. Граф является гипогамильтоновым, что означает, что хотя он не имеет гамильтонова цикла, удаление любой вершины делает его гамильтоновым, и это наименьший гипогамильтонов граф.
Как конечный связный вершинно-транзитивный граф, не имеющий гамильтонова цикла, граф Петерсена является контрпримером варианта гипотезы Ловаша, но каноническая формулировка гипотезы спрашивает о гамильтоновом пути и для графа Петерсена эта гипотеза выполняется.
Известны только пять связных вершинно-транзитивных графов без гамильтоновых циклов — полный граф K2, граф Петерсена, граф Коксетера и два графа, полученных из графов Петерсена и Коксетера путём замены каждой вершины треугольником [7]. Если G является 2-связным, r-регулярным графом с максимум 3r + 1 вершинами, то G является гамильтоновым или G является графом Петерсена [8].
Чтобы показать, что граф Петерсена не имеет гамильтонова цикла C, рассмотрим рёбра, соединяющие внутренний цикл из 5 вершин с внешним циклом. Если существует гамильтонов цикл, должно быть выбрано чётное число этих рёбер. Если выбрано только два ребра, их конечные вершины должны быть смежными в одном из циклов с 5 вершинами, что невозможно. Таким образом, должно быть выбрано 4 ребра. Предположим, что верхнее ребро не выбрано (все другие случаи аналогичны ввиду симметрии). Из 5 рёбер внешнего цикла два верхних ребра должны входить в гамильтонов цикл, так что два боковых ребра в цикл входить не должны, а тогда нижнее ребро должно входить в цикл. Два верхних ребра во внутреннем цикле должны быть выбраны, но тогда эти два ребра замыкают цикл, не являющийся полным, так что он не может быть частью гамильтонова цикла. Альтернативно, мы можем рассмотреть 3-регулярные графы с десятью вершинами, имеющими гамильтонов цикл, и показать, что ни один из этих графов не является графом Петерсена, путём нахождения цикла в каждом из них, более короткого, чем любой цикл графа Петерсена. Любой гамильтонов 3-регулярный граф с десятью вершинами состоит из цикла с десятью вершинами цикла C, плюс пять хорд. Если любая хорда соединяет две вершины вдоль C на расстоянии два или три друг от друга, то граф имеет 3-цикл или 4-цикл, а потому графом Петерсена быть не может. Если две хорды соединяют противоположные вершины цикла C на расстоянии четыре вдоль C, снова имеется 4-цикл. Остаётся только случай лестницы Мёбиуса , образованной соединением каждой пары противоположных сторон хордой, которая снова имеет 4-цикл. Поскольку обхват графа Петерсена равен пяти, он не может быть образован таким образом, а следовательно, не имеет гамильтонова цикла.
Раскраска
Граф Петерсена имеет хроматическое число 3, что означает, вершины графа могут быть раскрашены в три цвета, но не в два, таким образом, что никакое ребро не соединяет две вершины одного цвета. Граф имеет предписанную раскраску?! в 3 цвета согласно теореме Брукса для предписанных раскрасок. Граф Петерсена имеет хроматический индекс 4, т.е. раскраска рёбер требует четырёх цветов. Иными словами, граф не является суммой трех 1-факторов, что показал ещё сам Петерсен [9]. Доказательство этого требует проверки четырёх случаев, чтобы показать, что не существует раскраска рёбер в 3 цвета. Как связный кубический граф без мостов с хроматическим индексом четыре, граф Петерсена является снарком. Это наименьший возможный снарк и был единственным известным снарком с 1898 по 1946. Теорема о снарках, высказанная в виде гипотезы Татом и доказательство которой было объявлено в 2001 Робертсоном, Сандерсом, Сеймуром и Томасом [10], утверждает, что любой снарк имеет граф Петерсена в качестве минора.
Кроме того, граф имеет дробный хроматический индекс 3, что подтверждает, что разница между хроматическим индексом и дробным хроматическим индексом может быть равна 1. Давняя гипотеза Голдберга — Сеймура предполагает, что это наибольшая возможная разница.
Число Туэ?! (вариант хроматического индекса) графа Петерсена равно 5.
Граф Петерсена требует по меньшей мере трёх цветов в любой (возможно, несобственной) раскраске, которая нарушает все симметрии. То есть, характерное число раскраски[англ.] графа равно трём. За исключением полных графов, есть только кнезеровский граф, характерное число которого не равно двум [11].
Другие свойства
Граф Петерсена:
- является 3-связным, а потому рёберно 3-связным и не имеющим мостов. См. Связный граф.
- имеет число независимости 4 и является 3-дольным. См. Задача о независимом множестве.
- является кубическим графом, имеет число доминирования 3, имеет совершенное паросочетание и 2-фактор.
- имеет 6 различных совершенных паросочетаний.
- является наименьшим кубическим графом с обхватом 5. (Это единственная -клетка. Фактически, поскольку граф имеет только 10 вершин, он является единственным -графом Мура.) [12].
- имеет радиус 2 и диаметр 2. Это наибольший кубический граф с диаметром 2 [13]
- имеет спектр графа −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
- имеет 2000 остовных деревьев, больше чем любой кубический граф с 10 вершинами [14]
- имеет хроматический многочлен?! [15]
- имеет характеристический многочлен , что делает его целым графом?! — графом, спектр которого полностью состоит из целых чисел.
- Между любыми двумя вершинами существует единственный путь длины не более двух.
Гипотеза Петерсена о раскраске
Согласно Девосу, Нешетрилу и Распауду «Цикл графа G — это множество C E(G), такое что любая вершина графа (V(G),C) имеет чётную степень. Если G,H являются графами, мы определяем отображение φ: E(G) —> E(H) как непрерывное по циклам, если прообраз любого цикла в H является циклом в G. Обворожительная гипотеза Иегера утверждает, что любой граф без мостов имеет непрерывное по циклам отображение в граф Петерсена. Йегер показал, что если гипотеза верна, то верна и гипотеза о двойном покрытии циклами длины 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-Δ. Полный граф K6 также входит в петерсеново семейство. Эти графы образуют запрещённые миноры для вложимых без зацеплений графов, графов, которые могут быть вложены в трёхмерное пространство таким образом, что никакие два цикла в графе не зацеплены [19]
Граф Клебша состоит из копий графа Петерсена как порождённых подграфов — для каждой вершины v графа Клебша десять не являющихся соседями вершин v порождают копию графа Петерсена.
Примечания
- ↑ The Petersen graph.
- ↑ Kempe, 1886.
- ↑ Knuth, 2011.
- ↑ Babai, 1995, с. 1447–1540.
- ↑ According to the Список Фостера.
- ↑ Как указано, это допускает, что графы Кэли не обязательно связен. Некоторые источники требуют, чтобы графы Кэли были связными, что делает пустой граф[англ.]* с двумя вершинами является наименьшим вершинно-транзитивным графом, не являющимся графом Кэли. По определению, данному в этих источниках, граф Петерсена является наименьшим связным вершинно-транзитивным графом, не являющимся графом Кэли.
- ↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)."
- ↑ Holton, Sheehan, 1993, с. 32.
- ↑ Харари, 2003, с. 113.
- ↑ Pegg, 2002, с. 1084–1086.
- ↑ Albertson, Boutin, 2007, с. R20.
- ↑ Hoffman, Singleton, 1960, с. 497–504.
- ↑ Это следует из факта, что граф является графом Мура, поскольку граф Мура является наибольшим возможным регулярным графом с такой степенью вершин и диаметром (Hoffman & Singleton 1960).
- ↑ Jakobson, Rivin, 1999; Valdes, 1991. Кубические графы с 6 и 8 вершинами, на которых число остовных деревьев максимизируется, это лестницы Мёбиуса.
- ↑ Biggs, 1993.
- ↑ DeVos, Nešetřil, Raspaud, 2007, с. 109–138.
- ↑ Coxeter, 1950.
- ↑ Watkins, 1969.
- ↑ 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. — Т. 49, вып. 9. — doi:10.1109/TED.2002.1003756. — .
- 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.
- 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. — Т. 56, вып. 5. — С. 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.
- 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 PlanetMath
- Weisstein, Eric W. Petersen Graph (англ.) на сайте Wolfram MathWorld.
- Petersen Graph в Энциклопедии целочисленных последовательностей
 | Для улучшения этой статьи желательно:
|