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

Граф Петерсена
	Граф Петерсена зазвичай зображують у вигляді п'ятикутника з п'ятикутником всередині, з п'ятьма спицями.
Названо на честь	Юліуса Петерсена
Вершин	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.

Див. такожРедагувати

ПриміткиРедагувати

↑ Brouwer, Andries E. The Petersen graph. Архів оригіналу за 8 червня 2011. Процитовано 25 лютого 2011.
↑ 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.
↑ Knuth, Donald E. The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching.

[1] Brouwer, Andries E. The Petersen graph. Архів оригіналу за 8 червня 2011. Процитовано 25 лютого 2011.

[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.

[1]

[2]

[3]