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

Граф Петерсена — это неориентированный граф с 10 вершинами и 15 рёбрами, известный в теории графов как классический пример контрпримера ко многим гипотезам и объект, обладающий рядом уникальных свойств. Назван в честь датского математика Юлиуса Петерсена, который впервые описал его в 1898 году. Граф Петерсена является одним из наиболее изучаемых графов в комбинаторике и часто используется для иллюстрации сложных концепций, таких как гамильтоновость, планарность и раскраска.

Определение и свойства

Граф Петерсена обозначается как \( GP(5,2) \) или \( K_{5,2} \) и относится к классу циркулянтных графов. Его вершины можно расположить на двух концентрических окружностях (внешней и внутренней) по пять вершин на каждой, причём каждая вершина внешней окружности соединена с двумя соседними вершинами на той же окружности, а также с одной вершиной внутренней окружности, образуя структуру, напоминающую пятиугольную звезду (пентаграмму). Внутренние вершины также соединены между собой в цикл.

Основные характеристики

• Количество вершин: 10.
• Количество рёбер: 15.
• Степень вершин: 3 (граф является 3-регулярным, то есть кубическим).
• Диаметр: 2 (максимальное расстояние между любыми двумя вершинами равно 2).
• Обхват: 5 (длина наименьшего цикла равна 5). Это означает, что в графе нет треугольников и четырёхугольников.
• Хроматическое число: 3 (граф можно раскрасить в три цвета, но не в два).
• Хроматический индекс: 4 (для рёберной раскраски требуется 4 цвета, что делает его единственным кубическим графом с хроматическим индексом 4, не содержащим мостов).
• Симметричность: Граф Петерсена является вершинно-транзитивным (для любых двух вершин существует автоморфизм, переводящий одну в другую) и рёберно-транзитивным, но не дистанционно-транзитивным. Его группа автоморфизмов изоморфна симметрической группе \( S_5 \) и имеет порядок 120.

Матричное представление

Матрица смежности графа Петерсена — это симметричная матрица размером 10×10, где на пересечении строки и столбца стоит 1, если вершины соединены ребром, и 0 в противном случае. Спектр графа (набор собственных значений матрицы смежности) состоит из чисел: 3 (кратность 1), 1 (кратность 5), −2 (кратность 4). Это делает его сильно регулярным графом с параметрами (10, 3, 0, 1).

История

Граф был впервые описан Юлиусом Петерсеном в 1898 году в статье «Sur le théorème de Tait» (О теореме Тейта), посвящённой проблеме раскраски рёбер кубических графов. Петерсен использовал этот граф как контрпример к гипотезе о том, что любой кубический граф можно раскрасить в три цвета по рёбрам (гипотеза, связанная с теоремой о четырёх красках). Впоследствии граф стал известен как «граф Петерсена» и приобрёл широкую известность в математической литературе.

Классификация и обобщения

Циркулянтный граф

Граф Петерсена является циркулянтным графом \( C_{10}(1, 2) \), где вершины расположены в цикле, и каждая вершина соединена с вершинами, отстоящими на 1 и 2 шага. Однако он не является графом Кэли для какой-либо группы, так как не существует группы, порождённой двумя элементами, которая давала бы такую структуру.

Граф Кнезера

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

Обобщения

Существуют обобщения графа Петерсена, такие как графы Петерсена общего вида \( GP(n, k) \), где \( n \) — количество вершин на каждой окружности, а \( k \) — шаг соединения. Например, \( GP(6, 2) \) — это граф, известный как «граф Петерсена для шестиугольника». Однако только \( GP(5, 2) \) обладает всеми уникальными свойствами классического графа Петерсена.

Применение и значение

Граф Петерсена служит контрпримером ко многим гипотезам в теории графов. Например:

• Гипотеза Тейта: Петерсен показал, что его граф не является 3-рёберно-раскрашиваемым, опровергая утверждение, что любой кубический граф без мостов можно раскрасить в три цвета.
• Гипотеза о гамильтоновости: Граф Петерсена не является гамильтоновым (не содержит цикла, проходящего через все вершины ровно один раз), хотя он является 3-регулярным и 2-связным. Это опровергает предположение, что любой 2-связный кубический граф гамильтонов.
• Планарность: Граф Петерсена не является планарным (его нельзя нарисовать на плоскости без пересечения рёбер). Он содержит минор \( K_{3,3} \) (полный двудольный граф с тремя вершинами в каждой доле), что доказывает его непланарность по теореме Вагнера.

В математическом образовании

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

Интересные факты

• Граф Петерсена является единственным кубическим графом с обхватом 5 и 10 вершинами, что делает его уникальным в своём классе.
• Он является графом-мультиграфом, то есть не содержит петель и кратных рёбер.
• В 1970-х годах граф Петерсена был использован для построения контрпримера к гипотезе о том, что любой 3-регулярный граф без мостов имеет совершенное паросочетание (гипотеза, доказанная позже для всех графов, кроме этого).
• Граф Петерсена является самодвойственным, если рассматривать его как плоский граф (хотя он не планарный, его двойственный граф изоморфен ему самому).

Критика и ограничения

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

Источники

• Petersen, J. (1898). «Sur le théorème de Tait». Intermediaire des Mathematiciens.
• Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
• Harary, F. (1969). Graph Theory. Addison-Wesley.
• Diestel, R. (2017). Graph Theory. Springer.