У деяких прикладних задачах потрібно розташувати граф на двовимірної поверхні (площину, куля, багатогранник, тор і ін.) Таким чином, щоб ребра графа не перетинали один одного.
Визначення. Планарним називають граф, який може бути зображений на площині так, щоб його ребра не перетиналися. Геометричне зображення планарного графа, при якому його ребра не перетинаються, називають плоским графом.
Приклад 1. Розглянемо приклади планарних графів і їх плоскі зображення:
Рис.2.12. Приклади планарних графів і їх плоскі зображення
Кожен планарний граф також може укладений без перетину ребер на сфері або інших видах поверхонь. Критерієм планарності графів є
Теорема 2.11. Понтрягіна-Куратовского.
Граф планарії тоді і тільки тоді, коли він не містить подграфов, гомеоморфних графам К5 і К3,3.
Приклад 2. Визначити планарність графа К4,4.
Рішення. Оскільки граф К4,4 містить в якості подграфа К3,3. то по теоремі Понтрягіна-Куратовского він не планарії.
Визначення. Частина площини, обмежену простим циклом плоского графа і не містить в собі інших вершин і ребер, називають його гранню. Цикл, що обмежують грань, називають кордоном межі. Грані, що знаходяться всередині плоского графа, називають внутрішніми. грань, яка перебуває зовні -Зовнішній.
Кожне ребро плоского графа належить рівно обидва боки. Його видалення призводить до того, що дві грані зливаються в одну.
Для плоских графів (псевдографів) справедлива
Теорема 2.12. Формула Ейлера. Якщо n - кількість вершин, m - кількість ребер, r - кількість граней деякого зв'язкового плоского графа G. то
Зауваження. Формула Ейлера може бути застосована тільки до плоских графам, у яких можна виділити межі.
Приклад 3. Перевірити здійснимість формули Ейлера дляплоского графа G = (V, X), V = (1, 2, 3, 4, 5, 6), X = ((1, 2), (1, 3), (1 , 4), (2, 3), (3, 4), (4, 5), (4, 6), (5, 6)) на рис.2.13.
Рішення. Характеристики графа наступні: n = 6, m = 8, r = 4 (3 внутрішніх межі і одна зовнішня). Підставляючи в формулу Ейлера, отримаємо: 4 + 6 - 8 = 2.
Приклад 4. Довести, що граф К5 НЕ планарії.
Рішення. Основні характеристики графа наступні: n = 5, m = С 2 5 = (5 × 4) / (2 × 1) = 10. Якщо допустити планарність розглянутого графа, то має існувати його плоске зображення. З формули Ейлера знайдемо число граней в плоскому зображенні: r = 2 - n + m = 2 5 + 10 = 7. Так як кожна грань повного графа повинна містити не менше трьох ребер, то загальне число ребер в гранях (з урахуванням повторів при підрахунку) має бути не менше 21. Оскільки одне ребро в плоскому графі може входити до складу рівно двох граней, то загальне число ребер має бути не менше 11. Проте, m = 10.Отсюда випливає, що плоска укладання графа К5 не існує. Отже, він не планарії, що й треба було довести.
1. Довести з використанням формули Ейлера непланарность графа К3,3.
2. Довести, що граф К6 НЕ планарії двома способами
1) за допомогою теореми Понтрягіна-Куратовского,
2) за допомогою формули Ейлера.
3. Перевірити справедливість формули Ейлера для дерев.
4. Яку мінімальну кількість ребер необхідно видалити з плоского графа, для того, щоб перетворити його в дерево? Відповідь обґрунтувати.
5. Чи можна побудувати непланарний граф з 4 вершинами?
6. Побудувати непланарний граф з 6 вершинами, що не містить К3,3.
7. Перевірити планарність графа К2,4.
8. Перевірити планарність куба В 3.
9. Перевірити планарність куба В 4.
10. Перевірити планарність графа на рис.2.14.
Рис.2.14. Граф до Задачі 10
КОНТРОЛЬНІ ЗАВДАННЯ ПО ТЕМІ