Плоскі і планарні графи
Плоский граф - це граф, який намальований на площині так, що ніякі два його ребра не перетинаються.
Планарний граф - це граф, ізоморфний плоскому графу.
На малюнку а) - планарний, але не плоский, граф, б) плоский граф.
Кожен плоский граф розбиває площину на межі: внутрішні - обмежені і зовнішню - необмежену.
Вивчення планарних графів було розпочато Ейлером в його дослідженнях поліедров. Наступна формула Ейлера - це класичний результат в математиці:, де - число вершин, - число ребер, - число граней багатогранника. Формула Ейлера справедлива і в більш загальному випадку для плоскої карти - зв'язкового плоского графа, що розглядається разом з усіма його гранями.
Теорема. Нехай плоска карта має вершин, ребер і граней. Тоді має місце рівність:
Доведення. Застосуємо індукцію по числу ребер.
Якщо, то формула (1) прийме наступний вигляд:.
Припустимо, що для всіх плоских карт з числом ребер не більш формула (1) вірна. Плоска карта з числом ребер виходить з плоскою карти з числом ребер двома способами:
1) додатком нової вершини, яка з'єднується ребром з одного зі старих вершин;
2) з'єднанням ребром двох не суміжні вершин.
У першому випадку формула (1) перевіряється наступним чином:
.
У другому випадку з'являється нова грань і формула (1) перевіряється наступним чином:
.
Слідство 1. Якщо в -Карта кожна грань утворена циклом з вершин, то
Доведення. Число ребер, що належать кожній грані одно. Значить, число вершин, підраховуваних при кожній грані, так само. При цьому кожне ребро підраховується двічі, тому число перераховуваних вершин одно. Отримаємо рівність. Підставами в (1) і знайдемо (2).
Теорема Куратовского. Граф планарії тоді і тільки тоді, коли не містить подграфа, гомеоморфного або.
35. Повні графи. Граф K4 планарний і граф K5 НЕ планарний.
Максимальним планарним графом називається планарний граф, який при додаванні будь-якого ребра перестає бути планарним.
З визначення випливає, що в максимально планарном графі всі грані є трикутниками (гранями з трьома вершинами):
якщо грань містить чотирикутник (або багатокутник з великим числом сторін), то можна додати ребро, що не міняє планарність графа, але позбавляє властивості графа бути максимально планарним графом.
Приклад. Наступного граф можна додати тільки одне ребро, після якого цей граф звертається в граф.
Лемма. Якщо - планарний -граф і, то
.
Доведення. Найбільшим числом ребер в плоскому графі володіє граф, у якого всі грані - трикутники. У максимальному планарном графі всі грані - трикутники. Підставами в (2). Отримаємо.
Теорема. Граф не планарний.
Доведення. Якщо (5,10) -граф планарний, то не виконується лема:.
36. Дводольні графи. Граф K2,3 планарний і граф K3,3 НЕ планарний.
Граф називається дводольним-графом. якщо безліч вершин складається з двох непустих частин, (,), всередині яких немає ребер.
Якщо при цьому все вершин з з'єднані з усіма вершинами з, то граф називається повним дводольним-графом і позначається через.
Наведемо повні дводольні графи з числом вершин не більше 4:
Максимальним планарним дводольним графом називається планарний двочастковий граф, який при додаванні будь-якого ребра перестає бути планарнимдвудольним графом.
Якщо - максимальний планарний двочастковий граф, то кожна її грань є чотирикутником:
Приклад. Наступного граф можна додати тільки одне ребро, після якого цей граф звертається в граф:
Лемма. Якщо - планарний двочастковий граф, то -граф, то
.
Доведення. Найбільшим числом ребер в плоскому дводольному графі володіє граф, у якого всі грані - чотирикутники. У максимальному планарном графі всі грані - чотирикутники. Підставами в (2). Отримаємо.
Теорема. Графи і не планарні.
Доведення. Якщо (6,9) -граф планарний, то не виконується лема:.