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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф Петерсена
Petersen1 tiny.svg
Граф Петерсена зазвичай зображують у вигляді п'ятикутника з п'ятикутником всередині, з п'ятьма спицями.
Названий на честь Юліуса Петерсена
Вершин 10
Ребер 15
Радіус 2
Діаметр 2
Обхват 5
Автоморфізм 120 (S5)
Хроматичне число 3
Хроматичний індекс 4
Дробово-хроматичний індекс 3
Властивості Кубічний
Сильно регулярний
Відстанево-транзитивний

Граф Петерсенанеорієнтований граф з 10 вершинами і 15 ребрами. Це невеличкий граф, який слугує корисним прикладом або контрприкладом для багатьох проблем в теорії графів. Названий на честь Юліуса Петерсена, який у 1898 побудував його як найменший безмостовий кубічний граф з неможливістю трикольорового розфарбування ребер.[1] Хоча граф звичайно приписують Петерсену, він з'явився на 12 років раніше, в 1886.[2]

Дональд Кнут стверджує, що граф Петерсена це «видатна форма, що слугує контрприкладом для багатьох оптимістичних пророцтв про те, що може бути правильним для графів загалом.»[3]

Побудова[ред.ред. код]

Граф Петерсена як граф Кнесера KG_{5,2}

Граф Петерсена — це доповнення лінійного графа для K_5. Це також граф Кнесера KG_{5,2}; це значить, що він має по одній вершині для кожного 2-елементної підмножини 5-елементної множини, і дві вершини зв'язані ребром тоді і тільки тоді, якщо відповідні двохелементні підмножини не пересікаються між собою. Як граф Кнесера форми KG_{2n-1,n-1} — це приклад непарного графу.

Вкладення[ред.ред. код]

Щоб отримати K_{3,3} зведіть голубі до найближчих зелених і між собою дві червоні

Граф Петерсена — непланарний. Будь-який непланарний граф як мінори або повний граф K_5, або повний дводольний граф K_{3,3}, але граф Петерсена має як мінори їх обох. Мінор K_5 можна отримати видаленням ребер досконалого парування, наприклад, п'яти коротких ребер на малюнку.

Кількість перетинів графа Петерсена дорівнює 2

Найпоширеніший малюнок графа Петерсена, пентаграма всередині пентагона, має п'ять перетинів. Однак, це найкращий малюнок з огляду на кількість перетинів; існує інше зображення лише з двома перетинами. На торі граф Петерсена можна намалювати без перетинів; отже його зорієнтований рід 1.

Примітки[ред.ред. код]

  1. Brouwer, Andries E., The Petersen graph, http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html 
  2. Kempe, A. B. (1886), «A memoir on the theory of mathematical form», Philosophical Transactions of the Royal Society of London 177: 1–70, doi:10.1098/rstl.1886.0002 
  3. Knuth, Donald E., The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching