график Петерсена

Кубический граф с 10 вершинами и 15 ребрами

В математической области теории графов граф Петерсена представляет собой неориентированный граф с 10 вершинами и 15 ребрами . Это небольшой граф, который служит полезным примером и контрпримером для многих задач теории графов. Граф Петерсена назван в честь Юлиуса Петерсена , который в 1898 году сконструировал его как наименьший кубический граф без мостов и без трехрёберной раскраски. ^{[1] [2]}

Хотя этот график обычно приписывают Петерсену, на самом деле он впервые появился 12 лет назад в статье А. Б. Кемпе  (1886). Кемпе заметил, что ее вершины могут представлять десять линий конфигурации Дезарга , а ее ребра представляют собой пары прямых, не пересекающихся ни в одной из десяти точек конфигурации. ^[3]

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

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

Конструкции

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

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

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

Вложения

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

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

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

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

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

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

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

Симметрии

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

Группа автоморфизмов графа Петерсена является симметрической группой ; действие на граф Петерсена следует из его построения в виде графа Кнезера . Граф Петерсена является ядром : каждый гомоморфизм графа Петерсена самому себе является автоморфизмом. ^[7] Как показано на рисунках, рисунки графа Петерсена могут демонстрировать пятистороннюю или трехстороннюю симметрию, но невозможно нарисовать граф Петерсена на плоскости таким образом, чтобы рисунок демонстрировал полную симметрию. группа графика. ${\displaystyle S_{5}}$ ${\displaystyle S_{5}}$

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

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

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

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

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

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

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

Раскраска

4-раскраска ребер графа Петерсена.

3-раскраска вершин графа Петерсена.

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

Граф Петерсена имеет хроматический индекс 4; для окраски краев требуется четыре цвета. Как связный кубический граф без мостов с хроматическим индексом четыре, граф Петерсена представляет собой снарк . Это наименьший возможный снарк, и он был единственным известным снарком с 1898 по 1946 год. Теорема о снаркке , результат, выдвинутый У.Т. Туттом и объявленный в 2001 году Робертсоном, Сандерсом, Сеймуром и Томасом, ^[9] утверждает, что каждый снарк имеет граф Петерсена как минор .

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

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

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

Другие объекты недвижимости

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

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

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

Эйлеровым подграфом графа называется подграф, состоящий из подмножества ребер графа , касающихся каждой вершины четное число раз. Эти подграфы являются элементами пространства циклов и иногда называются циклами. Если и являются любыми двумя графами, функция от ребер до ребер определяется как циклически непрерывная, если прообраз каждого цикла является циклом . Гипотеза Йегера утверждает, что каждый граф без мостов имеет циклически непрерывное отображение в граф Петерсена. Джегер показал, что из этой гипотезы следует гипотеза 5- циклов о двойном накрытии и гипотеза Берджа-Фалкерсона». ^[17] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$

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

Семья Петерсен .

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

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

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

Примечания

1. Как уже говорилось, предполагается, что графы Кэли не обязательно должны быть связными. Некоторые источники требуют, чтобы графы Кэли были связными, что делает пустой граф с двумя вершинами наименьшим вершинно-транзитивным графом, не являющимся графом Кэли; согласно определению, данному в этих источниках, граф Петерсена — это наименьший связный вершинно-транзитивный граф, не являющийся графом Кэли.
2. Это следует из того, что это граф Мура, поскольку любой граф Мура является максимально возможным регулярным графом со своей степенью и диаметром. ^[11]
3. Кубические графы с 6 и 8 вершинами, максимизирующие количество остовных деревьев, представляют собой лестницы Мёбиуса .

Рекомендации

1. Брауэр, Андрис Э. , График Петерсена
2. Петерсен, Юлиус (1898), "Sur le theorème de Tait", L'Intermédiaire des Mathématiciens , 5 : 225–227
3. Кемпе, AB (1886), «Мемуары по теории математической формы», Philosophical Transactions of the Royal Society of London , 177 : 1–70, doi : 10.1098/rstl.1886.0002, S2CID  108716533
4. Кнут, Дональд Э., Искусство компьютерного программирования; том 4, предварительный выпуск 0A. Черновой вариант раздела 7: Введение в комбинаторный поиск
5. Бабай, Ласло (1995), «Группы автоморфизмов, изоморфизм, реконструкция», у Грэма, Рональда Л .; Гретшель, Мартин ; Ловаш, Ласло (ред.), Справочник по комбинаторике, том. I, Северная Голландия, стр. 1447–1540, Следствие 1.8, заархивировано из оригинала 11 июня 2010 г..
6. Ройл, Г. «Кубические симметричные графы (перепись Фостера)». Архивировано 20 июля 2008 г. в Wayback Machine.
7. Кэмерон, Питер Дж. (2004), «Автоморфизмы графов», в Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (ред.), Темы алгебраической теории графов , Энциклопедия математики и ее приложений, том. 102, Издательство Кембриджского университета, Кембридж, стр. 135–153, номер документа : 10.1017/CBO9780511529993, ISBN. 0-521-80197-4, МР  2125091; см., в частности, стр. 153
8. Холтон, Д.А.; Шиэн, Дж. (1993), График Петерсена , издательство Кембриджского университета , стр. 32, ISBN 0-521-43594-3
9. Пегг, Эд-младший (2002), «Рецензия на книгу: Колоссальная книга по математике» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Бибкод : 2002ITED...49.1084A, doi :10.1109/TED.2002.1003756
10. Альбертсон, Майкл О.; Бутин, Дебра Л. (2007), «Использование определяющих наборов для различения графов Кнезера», Электронный журнал комбинаторики , 14 (1): R20, doi : 10.37236/938 , MR  2285824.
11. Хоффман, Алан Дж .; Синглтон, Роберт Р. (1960), «Графы Мура диаметром 2 и 3» (PDF) , IBM Journal of Research and Development , 5 (4): 497–504, doi : 10.1147/rd.45.0497, MR  0140437.
12. Ласло Ловас, Александр Шрийвер (1998), «Теорема Борсука для антиподальных связей и спектральная характеристика бессвязно встраиваемых графов» (PDF) , Труды Американского математического общества , 126 (5): 1275–1285, doi : 10.1090/ S0002-9939-98-04244-0, S2CID  7790459
13. Бэрд, Уильям; Беверидж, Эндрю; Бонато, Энтони; Коденотти, Паоло; Маурер, Аарон; МакКоли, Джон; Валева, Сильвия (2014), «О минимальном порядке графов k-cop-win», Вклад в дискретную математику , 9 (1): 70–84, arXiv : 1308.2841 , doi : 10.11575/cdm.v9i1.62207 , MR  3265753
14. Якобсон, Дмитрий; Ривин, Игорь (1999), О некоторых экстремальных задачах теории графов , arXiv : math.CO/9907050 , Bibcode : 1999math......7050J
15. Вальдес, Л. (1991), «Экстремальные свойства остовных деревьев в кубических графах», Congressus Numerantium , 85 : 143–160.
16. Биггс, Норман (1993), Алгебраическая теория графов (2-е изд.), Кембридж: Cambridge University Press, ISBN 0-521-45897-8
17. ДеВос, Мэтт; Нешетржил, Ярослав ; Распауд, Андре (2007), «О картах ребер, инверсия которых сохраняет потоки или напряжения», Теория графов в Париже , Trends Math., Базель: Birkhäuser, стр. 109–138, doi : 10.1007/978-3-7643-7400 -6_10, МР  2279171.
18. Коксетер, HSM (1950), «Самодвойственные конфигурации и регулярные графы», Бюллетень Американского математического общества , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5.
19. Уоткинс, Марк Э. (1969), «Теорема о раскрасках Тейта с применением к обобщенным графам Петерсена», Журнал комбинаторной теории , 6 (2): 152–164, doi : 10.1016/S0021-9800(69) 80116-Х
20. Бэйли, Розмари А. (1997), Обзоры по комбинаторике , Cambridge University Press, стр. 187, ISBN 978-0-521-59840-8

дальнейшее чтение

• Эксу, Джеффри; Харари, Фрэнк ; Кабелл, Джеральд (1981), «Числа пересечений некоторых обобщенных графов Петерсена», Mathematica Scandinavica , 48 : 184–188, doi : 10.7146/math.scand.a-11910.
• Ловас, Ласло (1993), Комбинаторные задачи и упражнения (2-е изд.), Северная Голландия, ISBN 0-444-81504-Х.
• Швенк, AJ (1989), «Перечисление гамильтоновых циклов в некоторых обобщенных графах Петерсена», Журнал комбинаторной теории , серия B, 47 (1): 53–59, doi : 10.1016/0095-8956(89)90064-6

Внешние ссылки

• Вайсштейн, Эрик В. , «График Петерсена», MathWorld
• Граф Петерсена в Электронной энциклопедии целочисленных последовательностей