Введение

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

В математической области теории графов граф Петерсена — это неориентированный граф с 10 вершинами и 15 ребрами. Это небольшой граф, который служит полезным примером и контрпримером для многих задач в теории графов. Граф Петерсена назван в честь Юлиуса Петерсена, который в 1898 году сконструировал его как наименьший связный кубический граф, не имеющий трехреберной раскраски. Хотя граф обычно приписывается Петерсену, он впервые появился 12 лет ранее, в работе Кемпе, где было отмечено, что его вершины могут представлять десять прямых конфигурации Дезарга, а его ребра — пары прямых, не пересекающихся ни в одной из десяти точек конфигурации. Дональд Кнут утверждает, что граф Петерсена — это «замечательная конфигурация, служащая контрпримером для многих оптимистических предположений о том, что может быть верно для графов в целом». Граф Петерсена также появляется в тропической геометрии. Конус над графом Петерсена естественным образом отождествляется с модульным пространством пяти отмеченных рациональных тропических кривых.

Строительство

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

Встраивания

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

Симметрии

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

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

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

Цветение

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

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

Эйлеров подграф графа — это подграф, состоящий из подмножества рёбер , касающихся каждой вершины чётное число раз. Эти подграфы являются элементами циклического пространства и иногда называются циклами. Если и — любые два графа, функция из рёбер в рёбра определяется как циклически непрерывная, если прообраз каждого цикла является циклом. Гипотеза Ягера утверждает, что каждый связный безмостовой граф имеет циклически непрерывное отображение на граф Петерсена. Ягер показал, что эта гипотеза влечёт за собой гипотезу двойного покрытия 5-циклами и гипотезу Берге — Фулкерсона.

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

Обобщенный граф Петерсена формируется путем соединения вершин правильного n-угольника с соответствующими вершинами звездного многоугольника с символом Шлефли {n/k}. Например, в этой нотации граф Петерсена выглядит следующим образом: он может быть сформирован соединением соответствующих вершин пятиугольника и пятиконечной звезды, при этом ребра звезды соединяют каждую вторую вершину. К обобщенным графам Петерсена также относятся n-призма, граф Дюрера, граф Мёбиуса-Кантора, додекаэдр, граф Дезаргеса и граф Науру. Семейство Петерсена состоит из семи графов, которые могут быть получены из графа Петерсена путем применения нуля или более преобразований ΔY или YΔ. Полный граф K6 также принадлежит семейству Петерсена. Эти графы образуют запрещенные миноры для графов, допускающих безсвязное вложение, то есть графов, которые можно вложить в трехмерное пространство таким образом, чтобы никакие два цикла в графе не были связаны. Граф Клебша содержит множество копий графа Петерсена в виде индуцированных подграфов: для каждой вершины v графа Клебша десять ее несоседних вершин индуцируют копию графа Петерсена.