6.7. Планарні графи

Визначення 6.48. Граф називається правильно укладеним на площині, якщо його графічне подання таке, що ребра графа перетинаються тільки в його вершинах.

Визначення 6.49. Граф називається плоским (планарним), якщо він ізоморфний деякому графу , правильно укладеному на площині. Тобто плоский граф – це граф, який можна правильно укласти на площині.

Приклад 6.25. Графи і , подані на рис. 6.43, ізоморфні. Граф ‑ правильно укладений на площині. Отже, дані графи - плоскі.

Рис. 6.43.

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

Визначення 6.50. Гранню планарного графа називається така максимальна ділянка площини, що будь-які дві її точки можуть бути з'єднані кривою, що не перетинає ребро графа.

Задача про можливості правильного укладання графа на площині є актуальною у зв'язку з використанням у радіотехніці друкованих схем. Інтегральні мікросхеми складаються із шарів мініатюрних мікросхем, удрукованих у пластину. Ці схеми наносяться на ізолятор у друкований спосіб і перетинання яких-небудь двох провідників, у непередбачуваних точках (не у вершинах графа), привело б до їх замикання. Тобто для друкування електричних схем просто необхідно, щоб графи (що їх зображують) були плоскими.

Задачі, пов'язані із плоскими графами, актуальні не тільки в радіотехніці. Приведемо класичну задачу про три міста і три джерела постачання. Нехай є три міста , і і три джерела життєзабезпечення: водонапірна башта , електростанція і станція магістрального газопроводу . Чи можна з'єднати ці міста із джерелами постачання водою, газом і електрикою так, щоб траншеї, прориті для цих ліній (на одній глибині) не перетиналися?

Ця задача зводиться до побудови плоского графа, ізоморфного графу, зображеному на рис. 6.44.

Рис. 6.44.

Відповідь на питання поставлене у сформульованій задачі негативна. Завжди можна намалювати 8 попарно неперетинаючихся ліній, а дев'ята обов'язково перетне одну із цих восьми.

Доведення неможливості такої побудови спирається на теорему, доведену Жорданом. Проілюструємо її в такий спосіб. Нехай ‑ безперервна замкнута лінія без самоперетинань (рис. 6.45). Ця лінія ділить площину на дві частини: зовнішню і внутрішню. Будь-які дві точки і із внутрішньої і зовнішньої частин відповідно можна з'єднати тільки лінією, що перетинає .

Рис. 6.45.

Позначимо граф, зображений на рис. 6.44 як . Замінимо граф йому ізоморфним (рис. 6.46).

Рис. 6.46.

З'єднати вершини і без перетинання вже проведених ребер неможливо, тому що точка лежить усередині області, обмеженої кривою , а точка ‑ поза зазначеної області. Отже, граф не є планарным.

Аналогічно доводиться непланарність повного графа (рис. 6.47).

Рис. 6.47.

Використовуючи графи і , можна сформулювати наступний критерій планарності графів.

Теорема 6.7. (Теорема Куратовського). Граф є планарним тоді і тільки тоді, коли він не містить підграф, ізоморфний графу або .

Існують і інші критерії планарності графів.

Теорема 6.8. Якщо ‑ зв'язний планарний граф, що містить вершин, ребер і граней, то повинна виконуватися умова .

За допомогою теореми 6.8 задача про життєзабезпечення трьох будинків (рис. 6.44) вирішується в такий спосіб. У графа шість вершин і дев'ять ребер: , , а кількість граней ‑ . Підставимо в умову . Умова теореми 6.8 не виконується. Отже, граф ‑ не планарний.

Лема 6.1. У довільному планарному графі з кількістю вершин не менше трьох має місце нерівність .

За допомогою леми 6.1 доведемо, що граф не планарний. Граф має п'ять вершин і десять ребер: , . Скористаємося умовою . Як бачимо, умова для графа не виконана, отже, граф не планарний.

Вправи:

1. Кожний з наведених на рис. 6.48 a) − i) графів перевірити на планарність. Аргументувати рішення.

а) б) в)

г) д) е)

ж) з) і)

Рис. 6.48.

2. Для кожного планарного графа із завдання 1 запропонувати правильне укладання його на площині.

3. Для кожного планарного графа із завдання 1 перевірити виконання умови .