Материал: discrete_mathematics

(г) Кількість циклів у графі G не менша ніж ν(G).

2.Описати всі дерева, які є самодоповнювальними графами.

3.Довести, що граф G зв'язний тоді й тільки тоді, коли він має кістякове дерево.

4.Довести, що граф (простий цикл парної довжини C2k) є

двочастковим графом.

5.Скільки ребер містить повний двочастковий граф Kn,m?

6.Довести, що будь-яке дерево є двочастковим графом. Які дерева є повними двочастковими графами?

7.Який вигляд має доповнення графа Kn,m?

8.Чи для кожного натурального числа k існує повний двочас-

тковий граф, кількість ребер якого дорівнює k (k ≥ 2)?

9. Чому дорівнюють діаметр і радіус повного двочасткового графа Kn,m?

4.8. Плоскі та планарні графи

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

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

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

Наприклад, граф на рис. 4.7 а – планарний, оскільки він ізоморфний графу, що зображений поруч (рис. 4.7 б). Простий цикл, дерево та ліс − також планарні графи.

181

Про планарні графи ка-

жуть, що вони укладаються

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

Отже, плоский граф розбиває всю множину точок площини на грані так, що кожна точка належить деякій грані. Зазначимо, що плоский граф має одну, причому єдину, необмежену грань (на рис. 4.8 це грань 5). Називатимемо її зовнішньою, а всі інші грані − внутрішніми.

Множину граней плоского графа позначатимемо через P. Степенем грані r називають довжину циклічного шляху, що

обмежує грань r, тобто довжину межі грані r (позначають r).

Приклад 4.15.

1. На рис. 4.8 зображено плоский граф із п'ятьма гранями.

2. Довести, щодляплоскогографаG = (V, E) виконуєтьсярівність

∑ r = 2 E .

r P

Кожне ребро плоского графа або розділяє дві різні грані, або лежить усередині однієї грані (напр.=, на рис. 4.8 це ребро (v5, v7)). Отже, кожне ребро графа G або входить у межі тільки двох гра-

182

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

ми, а T = (V, ET) − деяке його кістякове дерево. Дерево T має тільки одну грань (зовнішню). Кількість ребер дерева T становить | ET | = | V | − 1. Отже, для кістякового дерева T формула (4.3) виконується.

Послідовно проводитимемо в дереві T ребра графа G із множини E \ ET. При цьому на кожному кроці процедури кількість вершин |V | залишатиметься незмінною, а кількості ребер і граней (див. п. 4.7) одночасно збільшуватимуться на одиницю. Таким чином, формула Ейлера (4.3) виконується після кожної такої операції, тому вона справджується й для графа G, який отримаємо на завершення всієї процедури.

4. Довести, що для довільного зв'язного планарного графа G = (V, E) із не менше ніж трьома вершинами виконується нерівність

| E | ≤ 3|V | − 6.

Оскільки в графі G немає петель і кратних ребер, то степінь r будь-якої грані не менше 3, тобто

∑ r ≥ 3 P .

r P

Ураховуючи співвідношення з прикладу 4.15(2) і формулу Ейлера, маємо

∑ r = 2 E ≥ 3( E − V + 2),

r P

звідки |E| ≤ 3 |V | − 6.

5. Довести, що в будь-якому планарному графі є принаймні одна вершина, степінь якої не перевищує 5.

Якщо припустити, що степені всіх вершин планарного графа G = (V, E) більші ніж 5, то дістанемо нерівність

2 Е = ∑δ(v) ≥ 6 V ,

v V

яка суперечить результату попередньої задачі. ◄

183

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

Плоский зв'язний граф, кожну грань якого (включаючи й зовнішню) обмежено трикутником, називають тріангуляцією.

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

Приклад 4.16.

1. Чи існує планарний граф, який має:

(а) 7 вершин і 16 ребер; (б) 8 вершин і 18 ребер?

(а) Ні, оскільки для нього не виконується нерівність із прик-

ладу 4.15 (4).

(б) Так, це тріангуляція.

2. Довести, що будь-яка тріангуляція з n вершинами (n ≥ 3)

Доведемо, що графи K5 i K3,3 не є планарними.

Доведемо, що граф K5 непланарний. Припустимо супротивне, тобто що K5 = (V, E) − планарний граф. Тоді із прикладу 4.15(4) випливає, що | E | ≤ 3 |V | − 6. Однак для графа

K5 | E | = 10 i |V | = 5,

тобто має виконуватись 10 ≤ 3 5 − 6 = 9, що неможливо. Отже, припущення про те, що K5 – планарний граф, неправильне.

Аналогічно методом від супротивного доведемо, що граф K3,3 непланарний. У графі K3,3 жодні три вершини не є вершинами

r P

що неправильно для графа K3,3.

184

Значення графів K5 i K3,3 полягає в тім, що вони є єдиними істотно непланарними графами. Усі інші непланарні графи містять підграфи, подібні до K5 або K3,3. Характер цієї подібності розкривається за допомогою таких понять.

Нехай e = (v, w) – ребро графа G, а u не є вершиною G. Вилучимо ребро e з графа G і додамо до нього нові ребра e1 = (v, u) та e2 = (v, u). Цю операцію називатимемо підрозбиттям ребра e.

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

морфних K5 або K3,3.

У теорії графів існують також інші критерії планарності. Наведемо ще один з них.

Елементарним стягуванням графа G = (V, E) називають ви-

лучення в ньому деякого ребра (vi, vj) E та злиття вершин vi i vj в одну вершину v, причому v інцидентна всім тим відмінним від (vi, vj) ребрам графа G, які були інцидентні або вершині vi , або вершині vj.

Кажуть, що граф G стягується до графа G′, якщо G′ можна отриматиізG задопомогоюпослідовностіелементарнихстягувань.

Граф G з рис. 4.10 стягується до графа G′ поруч.

Критерій планарності можна сформулювати у вигляді такого твердження: граф планарний тоді й тільки тоді, коли він не містить підграфів, що стягуються до K5 або K3,3.

Наведені критерії дають змогу перевірки планарності графів. Існують алгоритми, які, установивши планарність графа, будують для нього можливе плоске укладання.

185