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

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

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

Якщо площину розрізати по ребрах плоского графа, вона розпадеться на зв'язкові частини, які називають гранями. Завжди є одна необмежена зовнішня грань, все решта межі називаються внутрішніми. Якщо в плоскому графі немає циклів, то у нього є тільки одна грань. Якщо ж цикли є, то межа кожній грані містить цикл, але не обов'язково є циклом. на Мал. 3.7 показаний плоский граф з п'ятьма занумерованих гранями. Кордон межі з номером 3 складається з двох циклів, а межа межі з номером 2 крім циклу довжини 5 включає ще дерево з трьох ребер.

Безлічі ребер, що утворюють кордону граней, можуть бути різними для різних плоских укладок одного і того ж графа. на Мал. 3.8 показані дві плоскі укладання одного графа. У лівій укладанні є дві грані, межі яких є простими циклами довжини 5. У правій укладанні таких граней немає, але є межі, обмежені циклами довжини 4 і 6. Однак число граней, як показує наступна теорема, не залежить від укладання, тобто . є інваріантом планарного графа.

Теорема 6 (формула Ейлера). Кількість граней в будь-якому плоскому укладанні планарного графа, що має вершин, ребер і компонент зв'язності, так само .

Доказ.

Доведемо спочатку твердження теореми при . Розглянемо зв'язний плоский граф . Якщо в ньому немає циклів, то є єдина грань, а , І формула вірна. Якщо ж є хоча б один цикл, то візьмемо будь-яке ребро , Що належить простому циклу . Це ребро належить кордоні двох граней, одна з яких цілком лежить всередині циклу , Інша - зовні. Якщо видалити ребро з графа, ці дві грані зіллються в одну. Граф , Отриманий з графа видаленням ребра , Очевидно, буде плоским і зв'язковим, в ньому на одне ребро і на одну грань менше, ніж в , А число вершин залишилося колишнім. Якщо в ще є цикли, то, видаливши ще одне цикловое ребро, отримаємо граф . Будемо продовжувати видалення циклових ребер до тих пір, поки не вийде зв'язний плоский граф без циклів, тобто дерево. У нього ребро і єдина грань. Значить, все було видалено ребер, а так як при видаленні кожного ребра число граней зменшувалася на одиницю, то в початковому графі було грані. Таким чином, формула вірна для будь-якого зв'язного плоского графа. Якщо граф незв'язний, то в компоненті зв'язності, що має вершин і ребер, як доведено вище, буде внутрішня грань. Підсумовуючи за всіма компонентами і додаючи 1 для обліку зовнішньої межі, переконуємося в справедливості формули в загальному випадку.

Слідство 1. Якщо в планарном графі вершин, , і ребер, то .

Доказ.

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

Слідство 1 дає необхідна умова планарності, яке в деяких випадках дозволяє встановити, що граф не є планарним. Розглянемо, наприклад, повний граф . У нього , , І ми бачимо, що нерівність з слідства 1 не виконується. Значить, цей граф непланарен. У той же час існують графи, які не є планарними, для яких нерівність слідства 1 виконується. Приклад - повний двочастковий граф . У нього 6 вершин і 9 ребер. Нерівність виконується, але ми зараз встановимо, що він непланарен. Зауважимо, що в цьому графі немає циклів довжини 3 (так як він двочастковий, в ньому взагалі немає циклів непарної довжини). Тому межа кожній грані містить не менше чотирьох ребер. Повторюючи міркування з докази слідства 1, але використовуючи нерівність замість , Отримуємо наступний результат:

для графа нерівність слідства 2 не виконується, і це доводить, що він непланарен.

Відомо кілька критеріїв планарності, сформулюємо без доведення два з них. Два графа називають гомеоморфними, якщо з них за допомогою подразбіенія ребер можна отримати ізоморфні графи. на Мал. 3.9 зображені гомеоморфні графи.

Сформулюємо без доведення два критерії планарності.

Теорема 7 (критерій Понтрягина-Куратовского). Граф планарії тоді і тільки тоді, коли у нього немає подграфов, гомеоморфних або .

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

Теорема 8 (критерій Вагнера). Граф планарії тоді і тільки тоді, коли у нього немає подграфов, які стягуються до або .

Відзначимо, що, незважаючи на зовнішню схожість двох теорем, які фігурують в них поняття гомеоморфізму і стягіваемості істотно розрізняються. на Мал. 3.10 зображений граф, який називають графом Петерсена. У ньому немає подграфа, гомеоморфного , Так як в графі кожна вершина має ступінь , А в графі Петерсена ступінь кожної вершини дорівнює . При видаленні вершин і ребер і подразбіеніі ребер ступеня вершин не збільшуються. У той же час легко бачити, що граф Петерсена можна перетворити в стяганням п'яти ребер.