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

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

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

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

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

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

Конструкции [ править ]

Граф Петерсена как граф Кнезера

{\ 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.

Симметрии [ править ]

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

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

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

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

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

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

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

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

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

Раскраска [ править ]

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

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

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

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

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

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

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

Другие свойства [ править ]

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

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

Гипотеза Петерсена о раскраске [ править ]

Согласно ДеВосу, Несетрилу и Распауду, цикл графа G - это такое множество, что каждая вершина графа ( V ( G ), C ) имеет четную степень. Если G , H представляют собой графики, мы определим отображение быть циклом непрерывной , если прообраз каждого цикла H является цикл G . Увлекательная гипотеза Джагера утверждает, что каждый граф без мостов имеет непрерывное по циклу отображение в граф Петерсена. Джагер показал, что из этой гипотезы следует гипотеза о 5- цикличном двойном покрытии и гипотеза Берге-Фулкерсона » ^[16]. $C\subseteq E(G)$ $\phi :E(G)\to E(H)$

Связанные графики [ править ]

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

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

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

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

Заметки [ править ]

^ Брауэр, Андрис Э. , Граф Петерсена
^ Кнут, Дональд Э., Искусство программирования; том 4, пре-пучок 0А. Черновик раздела 7: Введение в комбинаторный поиск
^ Бабай, Ласло (1995), "Группы автоморфизмов, изоморфизм, реконструкция", у Грэма, Рональда Л .; Грёчель, Мартин ; Ловас, Ласло (ред.), Справочник по комбинаторике , I , Северная Голландия, стр. 1447–1540, следствие 1.8, заархивировано из оригинала 11 июня 2010 г..
^ По данным переписи Фостера .
^ Как уже говорилось, это предполагает, что графы Кэли не обязательно должны быть связными. Некоторые источники требуют, чтобы графы Кэли были соединены, что делает пустой граф сдвумя вершинаминаименьшим транзитивным повершинам графом, не являющимся графом Кэли; согласно определению, данному в этих источниках, граф Петерсена - это наименьший связный вершинно-транзитивный граф, который не является графом Кэли.
^ Ройл, Г. "Кубические симметричные графы (перепись Фостера)". Архивировано 20 июля 2008 г. в Wayback Machine.
^ Холтон & Sheehan (1993) , стр 32.
^ Пегг, Эд, младший (2002), «Рецензия на книгу: Колоссальная книга математики» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Bibcode : 2002ITED ... 49.1084A , DOI : 10,1109 / TED.2002.1003756
^ Альбертсон, Майкл O .; Бутин, Дебра Л. (2007), "Использование определения наборов для различения кнезеровского графа", Электронный журнал Комбинаторики , 14 (1): R20, DOI : 10,37236 / 938 , МР 2285824 .
^ Хоффман, Алан Дж . ; Singleton, Роберт Р. (1960), "Мур графы с диаметром 2 и 3" (PDF) , IBM Журнал исследований и разработок , 5 (4): 497-504, DOI : 10,1147 / rd.45.0497 , MR 0140437 .
↑ Ласло Ловас, Александр Шрайвер (1998). «Теорема Борсука для антиподальных связей и спектральная характеристика беззвучно вложимых графов» (PDF) . Труды Американского математического общества . 126 (5): 1275–1285. DOI : 10.1090 / S0002-9939-98-04244-0 .
^ Бэрд, Уильям; Беверидж, Эндрю; Бонато, Энтони; Коденотти, Паоло; Маурер, Аарон; Макколи, Джон; Валева, Сильвия (2014), «О минимальном порядке графов k -cop-win» , Вклад в дискретную математику , 9 (1): 70–84, arXiv : 1308.2841 , MR 3265753
^ Это следует из того факта, что это граф Мура, поскольку любой граф Мура является максимально возможным регулярным графом с его степенью и диаметром ( Hoffman & Singleton 1960 ).
^ Якобсон и Ривин (1999) ; Вальдес (1991) . Кубические графы с 6 и 8 вершинами, максимизирующие количество остовных деревьев, являются лестницами Мебиуса .
^ Биггс, Норман (1993), алгебраическая теория графов (2-е изд.), Кембридж: Cambridge University Press, ISBN 0-521-45897-8
^ ДеВос, Мэтт; Нешетржил, Ярослав ; Распо, Андре (2007), «О граничных картах, обратные карты которых сохраняют потоки или напряжения», Теория графов в Париже , Trends Math., Базель: Birkhäuser, стр. 109–138, DOI : 10.1007 / 978-3-7643-7400 -6_10 , Руководство по ремонту 2279171 .
^ Кокстер (1950) ; Уоткинс (1969) .
Перейти ↑ Bailey, Rosemary A. (1997), Surveys in Combinatorics , Cambridge University Press, p. 187, ISBN 978-0-521-59840-8

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

Викискладе есть медиафайлы, связанные с графом Петерсена .

Эксу, Джеффри; Харари, Фрэнк ; Кабелл, Джеральд (1981), «Числа пересечения некоторых обобщенных графов Петерсена», Mathematica Scandinavica , 48 : 184–188, doi : 10.7146 / math.scand.a-11910.
Косетер, HSM (1950), "Автодуальные конфигурации и регулярные графы", Бюллетень Американского математического общества , 56 (5): 413-455, DOI : 10,1090 / S0002-9904-1950-09407-5.
Holton, DA; Sheehan, J. (1993), граф Петерсена , Cambridge University Press , DOI : 10,2277 / 0521435943 , ISBN 0-521-43594-3.
Якобсон, Дмитрий; Ривин, Игорь (1999), О некоторых экстремальных задачах теории графов , arXiv : math.CO/9907050
Кемпе, А.Б. (1886), «Мемуары по теории математической формы», Philosophical Transactions of the Royal Society of London , 177 : 1–70, doi : 10.1098 / rstl.1886.0002
Ловас, Ласло (1993), Комбинаторные задачи и упражнения (2-е изд.), Северная Голландия, ISBN 0-444-81504-X.
Петерсен, Юлиус (1898), "Sur le théorème de Tait", L'Intermédiaire des Mathématiciens , 5 : 225–227
Швенк, AJ (1989), "Перечисление гамильтоновых циклов в некоторых обобщенных графах Петерсена", Журнал комбинаторной теории , серия B, 47 (1): 53–59, DOI : 10.1016 / 0095-8956 (89) 90064-6
Вальдес, Л. (1991), "Экстремальные свойства остовных деревьев в кубических графах", Congressus Numerantium , 85 : 143–160.
Уоткинс, Марк Э. (1969), «Теорема о раскраске Тейта с приложением к обобщенным графам Петерсена», Журнал комбинаторной теории , 6 (2): 152–164, DOI : 10.1016 / S0021-9800 (69) 80116 -ИКС

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

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

[1] Брауэр, Андрис Э. , Граф Петерсена

[2] Кнут, Дональд Э., Искусство программирования; том 4, пре-пучок 0А. Черновик раздела 7: Введение в комбинаторный поиск

[3] Бабай, Ласло (1995), "Группы автоморфизмов, изоморфизм, реконструкция", у Грэма, Рональда Л .; Грёчель, Мартин ; Ловас, Ласло (ред.), Справочник по комбинаторике , I , Северная Голландия, стр. 1447–1540, следствие 1.8, заархивировано из оригинала 11 июня 2010 г..

[4] По данным переписи Фостера .

[5] Как уже говорилось, это предполагает, что графы Кэли не обязательно должны быть связными. Некоторые источники требуют, чтобы графы Кэли были соединены, что делает пустой граф сдвумя вершинаминаименьшим транзитивным повершинам графом, не являющимся графом Кэли; согласно определению, данному в этих источниках, граф Петерсена - это наименьший связный вершинно-транзитивный граф, который не является графом Кэли.

[6] Ройл, Г. "Кубические симметричные графы (перепись Фостера)". Архивировано 20 июля 2008 г. в Wayback Machine.

[7] Холтон & Sheehan (1993) , стр 32.

[8] Пегг, Эд, младший (2002), «Рецензия на книгу: Колоссальная книга математики» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Bibcode : 2002ITED ... 49.1084A , DOI : 10,1109 / TED.2002.1003756

[9] Альбертсон, Майкл O .; Бутин, Дебра Л. (2007), "Использование определения наборов для различения кнезеровского графа", Электронный журнал Комбинаторики , 14 (1): R20, DOI : 10,37236 / 938 , МР 2285824 .

[hs60-10] Хоффман, Алан Дж . ; Singleton, Роберт Р. (1960), "Мур графы с диаметром 2 и 3" (PDF) , IBM Журнал исследований и разработок , 5 (4): 497-504, DOI : 10,1147 / rd.45.0497 , MR 0140437 .

[11] Ласло Ловас, Александр Шрайвер (1998). «Теорема Борсука для антиподальных связей и спектральная характеристика беззвучно вложимых графов» (PDF) . Труды Американского математического общества . 126 (5): 1275–1285. DOI : 10.1090 / S0002-9939-98-04244-0 .

[12] Бэрд, Уильям; Беверидж, Эндрю; Бонато, Энтони; Коденотти, Паоло; Маурер, Аарон; Макколи, Джон; Валева, Сильвия (2014), «О минимальном порядке графов k -cop-win» , Вклад в дискретную математику , 9 (1): 70–84, arXiv : 1308.2841 , MR 3265753

[13] Это следует из того факта, что это граф Мура, поскольку любой граф Мура является максимально возможным регулярным графом с его степенью и диаметром ( Hoffman & Singleton 1960 ).

[14] Якобсон и Ривин (1999) ; Вальдес (1991) . Кубические графы с 6 и 8 вершинами, максимизирующие количество остовных деревьев, являются лестницами Мебиуса .

[biggs-15] Биггс, Норман (1993), алгебраическая теория графов (2-е изд.), Кембридж: Cambridge University Press, ISBN 0-521-45897-8

[16] ДеВос, Мэтт; Нешетржил, Ярослав ; Распо, Андре (2007), «О граничных картах, обратные карты которых сохраняют потоки или напряжения», Теория графов в Париже , Trends Math., Базель: Birkhäuser, стр. 109–138, DOI : 10.1007 / 978-3-7643-7400 -6_10 , Руководство по ремонту 2279171 .

[17] Кокстер (1950) ; Уоткинс (1969) .

[Bailey1997-18] Перейти ↑ Bailey, Rosemary A. (1997), Surveys in Combinatorics , Cambridge University Press, p. 187, ISBN 978-0-521-59840-8

[1]