Що таке граф Петерсена?
Граф Петерсена — це неорієнтований граф з 10 вершинами і 15 ребрами. Це з'єднаний кубічний граф без мостів. Граф Петерсена служить корисним прикладом або контрприкладом для багатьох проблем у теорії графів.
Історія графа Петерсена
Граф Петерсена названий на честь данського математика Юліуса Петерсена, який у 1898 році побудував його як найменший безмостовий кубічний граф з неможливістю триколірного розфарбування ребер. Однак граф з'явився на 12 років раніше, в 1886 році, у роботах німецького математика Альфреда Тайте.
Властивості графа Петерсена
Граф Петерсена має багато цікавих властивостей, зокрема:
- Кубічний граф: Кожна вершина має три ребра.
- Безмостовий граф: Видалення будь-якого ребра не роз'єднує граф.
- Неможливість триколірного розфарбування ребер: Не існує триколірного розфарбування ребер графа Петерсена, тобто неможливо призначити три кольори ребрам так, щоб ребра, що виходять з кожної вершини, мали різні кольори.
- Регулярний граф: Кожна вершина має однакову кількість ребер.
- Симетричний граф: Граф симетричний щодо свого центра, тобто існує автоморфізм, який переводить будь-яку вершину в будь-яку іншу вершину.
Застосування графа Петерсена
Граф Петерсена використовується для вивчення різних проблем і концепцій у теорії графів, зокрема:
- Теорія Рамсея: Граф Петерсена є прикладом графа, який не є графом Рамсея, тобто не існує підграфа з парною кількістю вершин, який можна розбити на два рівних незалежних набори.
- Теорія розфарбування графів: Граф Петерсена є прикладом графа, який неможливо триколірно розфарбувати ребра.
- Теорія матроїдів: Граф Петерсена може бути представлений як матроїд, який доводить зв'язок між теорією графів і теорією матроїдів.
Граф Петерсена — це важливий граф у теорії графів, який має широке застосування. Його корисним прикладом і контрприкладом для різних концепцій і проблем у цій галузі.
Часто задавані запитання
- Хто відкрив граф Петерсена?
- Які властивості має граф Петерсена?
- Навіщо використовують граф Петерсена?
- Чи можна триколірно розфарбувати ребра графа Петерсена?
- Чим корисний граф Петерсена в теорії графів?