3. Зв’язаність і планарність графів. Методи перевірки зв’язності і критерії планарності графів.

Озн. Двійка G=(V,E) наз. графом, якщо V — м-на вершин, а E — м-на ребер на м-ні V.

Озн. Послідовність ребер е_і1, е_і2,...е_ік є Е наз. шляхом або маршрутом, якщо кожна пара сусідніх ребер цієї послід. має спільну вершину.

Озн. Шлях наз. ланцюгом, якщо кожне ребро в ньому зустріч. не більше 1 разу.

Озн. Циклічний шлях наз. циклом, якщо він є ланцюгом; простим циклом, коли він є простим ланцюгом(серед його вершин нема однакових).

Озн. Вершини v1 і v2 наз. зв’язними, якщо між ними існує шлях, де v1— початок, v2— кінець.

Озн. G_i , G_i=( V_i,E_i) G_i наз. компонентами зв’язності графа G

E_i= E V_i⁽²⁾, V_i⁽²⁾ —м-на двовалентних м-н.

Озн. Граф наз. зв’язним, якщо всі його вершини зв’язні між собою.

Теорема. Довіл. неорієнтов. граф однозначно представляється у вигляді прямої суми зв’язних компонент.

Теорема. Для довіл. неорієнтов. граф G або він або його доповнення є зв’язним.

Теорема. Нехай G — зв’язний граф, G=(V,E) ,e є E, розглянемо G1=(V,E\{e}):

1) Якщо ребро е належало деякому циклу, то G1 також буде зв’язним.

2) Якщо ребро е не належ. ніякому циклу, то G1—незв’язний і має 2 компоненти зв’язності.

Теорема:G=(V,E) – довільний граф з n вершин, к- компонента зв’язності, m- кількість ребер, тоді:

доведення методом мат. Індукц.

Наслідок: Якщо в графі кількість ребер більша ніж , то такі графи є зв’язними.

Перевірка зв’язності графів.

Методи, які спираються на матрицю суміжності.

Теорема. Нехай А — матриця суміжності графа G=(V,E) з кількістю верщин w, тоді а_іj(к) - ел-т А_к дорівнює кількості шляхів із і в j довжини к в графі G

Доведення: Індукцією за к.

1. База індукції к=1, а_іj(1)= а_іj — 1, якщо є шлях довжини 1 з і в j; 0, якщо нема шляху довж. 1.

2. Індукційний крок, к=m-1, A^m=A^m-1A-матриці, k=m, а_іj^(m)= а_іt^(m-1) а_tj=

а_іj^(m-1) а_tj⁽¹⁾

Розглянемо окремий доданок цієї суми а_іt^(m-1) а_tj⁽¹⁾. за припущенням індукції перший множник — к-сть шляхів з і в t, другий— з t в j довжини 1, тоді їх добуток— це к-сть шляхів з і в j.

Озн. Граф наз повним, якщо між довільною парою вершин є ребро.

Озн. А*— матриця суміжності графа G*. Граф G буде зв’язним тоді і тільки тоді, коли в А* нема нульових ел-тів.

А*— матр. досяжності, зв’язності, зв’язку для G

Побудова А*.

Звести до побудови М⁽ⁿ⁾. простіше буде:

1) С&D логічне (бульове) множення матриць, С— матр. із 0 і 1

Здійснюється моження за законом: f_ij=(c_it d_tj). Отримуємо або 0 або 1. Доведення, як у попередньої теореми.

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

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

Озн. Граф наз. планарним, якщо він ізоморфний плоскому.

Граф є планарним т. і т. т., коли кожна його компонента є планарним графом.

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

Доведення: G=(V,E), нехай Т=(V,E_Т)—це його кістякове дерево. Тоді для кістякового дерева це співвідношення виконується, бо |p|=1, |E|=|V|-1.

Т G. Додаємо до кістякового дерева ребро, тоді к-сть граней збільшується на 1. І т. д. Приходимо до нашого G.

граф к3,3 граф к5

Теорема. Графи к5 і к3,3 не є планарними к5 к3,3

Доведення: к5. від супр. к5—планарний. Тоді за насл.2 (якщо |V|>=3, то для планарного графа виконується: |E|<=3|V|-6) |10|<=3*5-6 —протиріччя

к3,3. від супр. к3,3—планарний. Довжини циклів цього графа >=4.Тоді за Лемою(G—плоский граф, тоді сума степенів усіх граней цього графа дорівн. 2|E|) 2|E|>=4|p|=4(|E|-|V|+2), 2*9>=4*(9-6+2), 18>=20—протиріччя.

Усі непланарні графи містять у собі так чи інакше к5 чи к3,3.

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