Граф Петерсена
Эту статью необходимо исправить в соответствии с правилом Википедии об оформлении статей. |
Граф Петерсена — достаточно простой объект теории графов с интересными свойствами. Назван в честь Юлиуса Петерсена, датского математика.
Общая информация
Граф Петерсена является неориентированным кубическим графом. Его можно построить, взяв дополнение рёберного графа от полного 5-графа. Имеет 10 вершин и 15 рёбер. Сильно регулярен и рёберно регулярен, то есть, выбрав вершину или ребро можно отобразить граф на себя, переведя выбранный объект в любую вершину (ребро). Граф является клеткой и графом Мура. Его группа — S5. Конфигурация Дезарга в проективной геометрии соответствует дополнению графа Петерсена и соответственно имеет ту же группу S5.
Свойства
- Не является гамильтоновым, в то же время, результат удаления вершины — гамильтонов граф.
- Хроматическое число графа — 3.
- Хроматический класс (раскраска рёбер) — 4, иными словами, граф не является суммой трех 1-факторов, что показал ещё сам Петерсен.[1]
- При изображении на плоскости имеет не менее двух самопересечений.
- Между любыми двумя вершинами существует единственный путь длины не более двух.
См. также
Примечания
- ↑ Ф. Харари Теория графов стр. 113
Литература
- Ф. Харари Теория графов. — М.: УРСС, — 2003. — 300 с. — ISBN 5-354-00301-6.
- О. Оре Теория графов. — М.: УРСС, — 2008. — 352 с. — ISBN 978-5-397-00044-4.
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |