![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/languk-640px-Petersen1_tiny.svg.png&w=640&q=50)
Граф Петерсена
З Вікіпедії, безкоштовно encyclopedia
Граф Петерсена — неорієнтований граф з 10 вершинами і 15 ребрами. Це невеличкий граф, який слугує корисним прикладом або контрприкладом для багатьох проблем в теорії графів. Названий на честь Юліуса Петерсена, який у 1898 побудував його як найменший безмостовий кубічний граф з неможливістю триколірного розфарбування ребер.[1] Хоча граф звичайно приписують Петерсену, він з'явився на 12 років раніше, в 1886.[2]
Коротка інформація Граф Петерсена, Названо на честь ...
Граф Петерсена | |
---|---|
![]() Граф Петерсена зазвичай зображують у вигляді п'ятикутника з п'ятикутником всередині, з п'ятьма спицями. | |
Названо на честь | Юліуса Петерсена |
Вершин | 10 |
Ребер | 15 |
Радіус | 2 |
Діаметр | 2 |
Обхват | 5 |
Автоморфізм | 120 (S5) |
Хроматичне число | 3 |
Хроматичний індекс | 4 |
Дробово-хроматичний індекс | 3 |
Властивості | Кубічний Сильно регулярний Відстанево-транзитивний |
Закрити
Дональд Кнут стверджує, що граф Петерсена це «видатна форма, що слугує контрприкладом для багатьох оптимістичних пророцтв про те, що може бути правильним для графів загалом.»[3]