- Формула Ейлера [ правити | правити код ]
- Повний граф з п'ятьма вершинами [ правити | правити код ]
- «Будиночки і колодязі» [ правити | правити код ]
- Комп'ютерна перевірка на планарність [ правити | правити код ]
open wikipedia design.
Планарний граф - граф , Який може бути зображений на площині без перетину ребер . Інакше кажучи, граф планарії, якщо він ізоморфний деякого плоскому графу, тобто графу, зображеному на площині так, що його вершини - це точки площині, а ребра - непересічні криві на ній. Області, на які граф розбиває площину, називаються його гранями. Необмежена частина площині - теж грань, так звана зовнішня грань.
Формула Ейлера [ правити | правити код ]
Для зв'язкового плоского графа справедливо наступне співвідношення між кількістю вершин | V (G) | {\ Displaystyle | V (G) |} 
| V (G) | - | E (G) | + | F (G) | = 2. {\ displaystyle \ | V (G) | - | E (G) | + | F (G) | = 2.}
Воно було знайдено Ейлером в 1736 р [1] при вивченні властивостей опуклих багатогранників . Це співвідношення справедливо і для інших поверхонь з точністю до коефіцієнта, званого ейлеровой характеристикою . це інваріант поверхні, для площини або сфери він дорівнює двом, а, наприклад, для поверхні тора - нулю.
Формула має безліч корисних наслідків. По-перше, всі плоскі укладання одного графа мають однакову кількість граней. По-друге, якщо кожна грань обмежена не менше ніж трьома ребрами (за умови, що в графі більше двох ребер), а кожне ребро розділяє дві грані, то
3 | F (G) | ≤ 2 | E (G) | , {\ Displaystyle 3 | F (G) | \ leq 2 | E (G) |,}
отже,
| E (G) | ≤ 3 | V (G) | - 6, {\ displaystyle | E (G) | \ leq 3 | V (G) | -6,}
тобто, при більшій кількості ребер такий граф свідомо непланарен. Протилежне твердження невірно: в якості контрпримера можна взяти граф Петерсена . Звідси випливає, що в планарном графі завжди можна знайти вершину ступеня не більше 5.
Загальна формула також легко узагальнюється на випадок незв'язною графа:
| V (G) | - | E (G) | + | F (G) | = 1 + | C (G) | , {\ Displaystyle | V (G) | - | E (G) | + | F (G) | = 1 + | C (G) |,}
де | C (G) | {\ Displaystyle | C (G) |} 
Повний граф з п'ятьма вершинами [ правити | правити код ]
Лемма. повний граф з п'ятьма вершинами (К5) не можна укласти на площину.
Доведення. Для нього не виконується E ⩽ 3 V - 6 {\ displaystyle E \ leqslant 3V-6} 
«Будиночки і колодязі» [ правити | правити код ]
Завдання про трьох колодязях. Є три будинки і три криниці. Чи можна так прокласти доріжки між будинками і колодязями, щоб від кожного будинку до кожного колодязя вела доріжка, і ніякі дві доріжки не перетиналися б. Мости будувати не можна.
Лемма. повний двочастковий граф з трьома вершинами в кожній з часткою (К3,3) не можна укласти на площину.
Доведення. За формулою Ейлера граф має 5 граней.
З іншого боку: будь-яка грань (включаючи зовнішню) містить парне число ребер - а значить, не менше 4. Оскільки кожне ребро включається в рівно дві грані, виходить співвідношення 4 F ⩽ 2 E {\ displaystyle 4F \ leqslant 2E} 
Очевидно твердження: якщо граф G містить підграф, гомеоморфними K5 або K3,3, то його неможливо розкласти на площині. Виявляється, вірно і зворотне.
Граф планарії тоді і тільки тоді, коли він не містить подграфов, гомеоморфних повного графу з п'яти вершин (K5) або графу «будиночки і колодязі» (K3,3).
Теорему також можна сформулювати в наступному варіанті (іноді його називають « теорема Вагнера »).
Граф планарії тоді і тільки тоді, коли не містить подграфов, стягують в K5 або K3,3.
Комп'ютерна перевірка на планарність [ правити | правити код ]
Перший алгоритм, що відшукує підграф Куратовского за лінійний час, розроблений в 1974 році Хопкрофта і Тарьяном [2] .
- достатня умова - якщо граф містить повний двочастковий підграф K3,3 або повний підграф K5, то він є непланарним;
- необхідна умова - якщо граф непланарний, то він повинен містити більше 4 вершин, ступінь яких більше 3, або більше 5 вершин ступеня більше 2.
Розфарбування карти. Необхідно розфарбувати плоску карту заданим числом фарб так, що будь-які дві країни, які мають спільну ділянку кордону, мали різні кольори. Виявляється, що при відсутності анклавів , Ніколи не бракує чотирьох фарб, але це твердження надзвичайно складно довести, см. Проблема чотирьох фарб .
Випрямлення графа ( теорема Фари ). Будь-плоский граф можна перемалювати так, щоб він залишився плоским, а ребра стали відрізками прямих.
Граф укладається на деякій поверхні, якщо його можна на ній намалювати без перетину ребер. Укладений граф називається геометричним, його вершини - це точки поверхні, а ребра - лінії на ній. Області, на які граф розбиває поверхню, називаються гранями. Плоский граф - граф, покладений на площину.
число перетинів графа G - найменше число перетинів ребер плоского малюнка графа G. Таким чином, граф є планарним тоді і тільки тоді, коли його кількість перетинів дорівнює нулю.
тороїдальний граф - граф, який можна укласти на тор.
