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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Петерсена
Другое представление графа Петерсена

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

Общая информация[править | править вики-текст]

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

Свойства[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Ф. Харари Теория графов стр. 113

Литература[править | править вики-текст]