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

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

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

Побудова

Граф Петерсена як граф Кнесера $K{G}_{5,2}$

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

Геометрично, граф Петерсена є графом, утвореним вершинами і ребрами напівдодекаедра, тобто додекаедра з ототожненими протилежними вершинами, ребрами і гранями.

Вкладення

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

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

Число схрещень графа Петерсена дорівнює 2

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

Див. також

• Задача степеня — діаметра
• Напівікосаедр