Плоскі та планарні графи (реферат)

Реферат на тему:

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

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

Таким чином виникає поняття плоского графа.

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

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

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

Очевидними є такі твердження.

Лема 3.4. 1). Будь-який підграф планарного графа є планарним.

2). Граф є планарним тоді і тільки тоді, коли кожна його зв’язна
компонента ( планарний граф.

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

а)
б)

Рис.3.7

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

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

Рис.3.8

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

Множину граней плоского графа позначатимемо через P.

Степенем грані r називатимемо довжину циклічного шляху, що обмежує грань
r (тобто довжину межі грані r ); позначається (r.

Для плоского графа на рис.3.8 {v3,(v3,v2),v2,(v2,v4),v4,(v4,v3),v3} (
циклічний шлях для грані 1,
{v2,(v2,v5),v5,(v5,v7),v7,(v7,v5),v5,(v5,v8),
v8,(v8,v10),v10,(v10,v6),v6,(v6,v2),v2} ( циклічний шлях для грані 3.
Отже, (1=3 i (3=7.

(r=2 |E |.

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

Теорема 3.13. (теорема Ейлера). Для будь-якого зв’язного плоского графа
G =(V,E ) виконується рівність

|V |(|E |+|P |=2.
(3.3)

Доведення. Нехай G =(V,E ) зв’язний плоский граф з n = |V | вершинами, а
T =(V,ET) ( деяке кістякове дерево графа G. Очевидно, що дерево T має
тільки одну грань (зовнішню). Кількість ребер дерева T дорівнює
|ET |=|V |(1. Отже, для кістякового дерева T формула (3.3) виконується.

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

Наслідок 3.13.1. Кількість граней будь-якого плоского укладання
зв’язного планарного графа з n вершинами і m ребрами є величиною сталою
і дорівнює m (n +2, тобто |P |=|E | (|V |+2.

Інакше кажучи, число |P | є інваріантом для заданого планарного графа G,
тобто не залежить від способу укладання його на площині.

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

|E | ( 3 |V | ( 6.

(r ( 3 |P |.

(r=2 |E | ( 3( |E | ( |V |+2) і, нарешті, |E | ( 3 |V | ( 6.

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

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

?(v) ( 6 |V |, яка суперечить попередньому наслідку.

Формулу Ейлера можна узагальнити.

Наслідок 3.13.4. Для довільного планарного графа G =(V,E ) з k
компонентами зв’язності виконується

|V |(|E |+|P |= k +1.
(3.4)

Для доведення узагальненої формули Ейлера можна побудувати кістяковий
ліс F графа G, переконатись у тому, що для F наведена рівність
виконується (див. наслідок 3.11.3), відтак, повторити міркування теореми
3.13.

Цей наслідок можна довести й іншим методом.

Якщо Vi, Ei та Pi – відповідні множини вершин, ребер і граней i-ї
зв’язної компоненти графа G, то |Pi |=|Ei |(|Vi | +2. Спільних
внутрішніх граней різні компоненти не мають, а зовнішня грань для всіх
компонент єдина і рахується по одному разу для кожної з них. Тому
загальна кількість граней графа G дорівнюватиме

|Vi | +2k (

((k(1)=|E |(|V | +k+1.

Звідси дістанемо формулу (3.4).

Наслідок 3.13.5. Кількість внутрішніх граней довільного плоского графа G
дорівнює цикломатичному числу ((G ) графа G.

Щоб переконатись у справедливості цього твердження потрібно порівняти
означення цикломатичного числа ((G ) (див. розділ 9) та узагальнену
формулу Ейлера (3.4), взявши до уваги, що кількість внутрішних граней
дорівнює |P |(1.

?не можуть бути одночасно планарними, якщо кількість вершин у них не
менше 11.

з кількістю вершин |V | ( 11.

При дослідженні плоских графів особливе місце займають графи K5 i K3,3,
зображені на рис.3.9.

K5 K3,3

Рис.3.9

Теорема 3.14. Графи K5 i K3,3 не є планарними.

Доведення. Доведемо, що граф K5 не є планарним. Припустімо супротивне,
тобто, що K5=(V,E ) ( планарний граф. Тоді з наслідку 3.13.2 випливає,
що |E | ( 3 |V | ( 6. Однак, для графа K5 |E |=10 i |V |=5, тобто
повинно виконуватись 10 ( 3(5 ( 6 = 9, що неможливо. Отже, припущення
про те, що K5 планарний граф ( неправильне.

Аналогічно, методом від супротивного доведемо, що K3,3 не є планарним. В
графі K3,3 жодні три вершини не є вершинами трикутника. Отже, (r ( 4 для
всіх граней r (P. Припускаючи, що граф K3,3 планарний, з наслідку 3.13.1
отримаємо

(r ( 4 |P | = 4(5 = 20, тобто |E | ( 10, що невірно для графа K3,3.
Теорему доведено.

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

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

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

Приклад 3.9. На рис.3.10 зображено графи G i G (, при цьому G
стягується до G (.

G G (

Рис.3.10

Наведемо без доведення важливу теорему теорії графів.

Теорема 3.15 (теорема Куратовського). Граф G є планарним тоді і тільки
тоді, коли він не містить підграфів, що стягуються до K5 або K3,3.

Ця теорема лежала в основі перших алгоритмів перевірки планарності
графів. Однак час роботи таких алгоритмів був пропорційний |V |6. Згодом
були створені значно швидші алгоритми, що здійснювали перевірку
планарності графа G =(V,E ) за час O(|V |) [8]. У монографіях [2,8]
описані також процедури, які для планарних графів знаходять плоскі
укладання.

Список літератури

1. Харари Т. Теория графов.- М.,1973.

2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов
В.И., Тышкевич Р.И.- М., 1990.

3. Зыков А.А. Основы теории графов.- М., 1987.

4. Оре О. Теория графов.- М., 1980.

5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. Уилсон Р. Введение в теорию графов.- М., 1977

7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978

8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М.,1980

v13

v14

v10