планарний граф

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

Найпростіші властивості плоских графів

Формула Ейлера

Для зв'язкового плоского графа справедливо наступне співвідношення між кількістю вершин | V (G) | . ребер | E (G) | і граней | F (G) | (Включаючи зовнішню грань):

Воно було знайдено Ейлером в 1736 р [1] при вивченні властивостей опуклих багатогранників. Це співвідношення справедливо і для інших поверхонь з точністю до коефіцієнта, званого ейлеровой характеристикою. Це інваріант поверхні, для площини або сфери він дорівнює двом, а, наприклад, для поверхні тора - нулю.

Формула має безліч корисних наслідків. По-перше, всі плоскі укладання одного графа мають однакову кількість граней. По-друге, якщо кожна грань обмежена не менше ніж трьома ребрами (за умови, що в графі більше двох ребер), а кожне ребро розділяє дві грані. то

тобто, при більшій кількості ребер такий граф свідомо непланарен. Протилежне твердження не вірно: як контрпримера можна взяти граф Петерсена. Звідси випливає, що в планарном графі завжди можна знайти вершину ступеня не більше 5.

Загальна формула також легко узагальнюється на випадок незв'язною графа:

де | C (G) | - кількість компонент зв'язності в графі.

Два приклади непланарних графів

Повний граф з п'ятьма вершинами

Перший алгоритм, що відшукує підграф Куратовского за лінійний час, розроблений в 1974 році Хопкрофта і Тарьяном [2].

Ознаки непланарних графів

• достатня умова - якщо граф містить повний двочастковий підграф K3,3 або повний підграф K5. то він є непланарним;
• необхідна умова - якщо граф непланарний, то він повинен містити більше 4 вершин, ступінь яких більше 3, або більше 5 вершин ступеня більше 2.

Планарні графи в задачах

Розфарбування карти. Необхідно розфарбувати плоску карту заданим числом фарб так, що будь-які дві країни, які мають спільну ділянку кордону, мали різні кольори. Виявляється, що при відсутності анклавів. завжди досить чотирьох фарб, але це твердження надзвичайно складно довести, см. Проблема чотирьох фарб.

Випрямлення графа (теорема Фари). Будь-плоский граф можна перемалювати так, щоб він залишився плоским, а ребра стали відрізками прямих.

Граф укладається на деякій поверхні, якщо його можна на ній намалювати без перетину ребер. Укладений граф називається геометричним. його вершини - це точки поверхні, а ребра - лінії на ній. Області, на які граф розбиває поверхню, називаються гранями. Плоский граф - граф, покладений на площину.