Граф Петерсена — достаточно простой объект теории графов с интересными свойствами. Назван в честь Юлиуса Петерсена, датского математика.

Общая информация

Граф Петерсена является неориентированным кубическим графом. Его можно построить, взяв дополнение рёберного графа от полного 5-графа. Имеет 10 вершин и 15 рёбер. Сильно регулярен и рёберно регулярен, то есть, выбрав вершину или ребро можно отобразить граф на себя, переведя выбранный объект в любую вершину (ребро). Граф является клеткой и графом Мура. Его группа — S₅. Конфигурация Дезарга в проективной геометрии соответствует дополнению графа Петерсена и соответственно имеет ту же группу S₅.

Свойства

• Не является гамильтоновым, в то же время, результат удаления вершины — гамильтонов граф.
• Хроматическое число графа — 3.
• Хроматический класс (раскраска рёбер) — 4, иными словами, граф не является суммой трех 1-факторов, что показал ещё сам Петерсен.^[1]
• При изображении на плоскости имеет не менее двух самопересечений.
• Между любыми двумя вершинами существует единственный путь длины не более двух.

См. также

• Планарный граф

Примечания

Литература

• Ф. Харари Теория графов. — М.: УРСС, — 2003. — 300 с. — ISBN 5-354-00301-6.
• О. Оре Теория графов. — М.: УРСС, — 2008. — 352 с. — ISBN 978-5-397-00044-4.