Графи та їх застосування

Ейлер підрахував число ребер, що виходить з кожної вершини графа (рис.1.2.). З вершин В, С і Д виходить по три ребра, а з вершини А – п’ять ребер. Вершини графа, з яких виходить непарна кількість ребер, він назвав непарними вершинами, а вершини, з яких виходить парна кількість ребер, - парними. Всі вершини даного графа виявились непарними.

В ході розв’язання цієї задачі Ейлер встановив наступні чотири властивості зв’язного графа:

1. Кількість непарних  вершин графа завжди парна.  Неможливо зобразити граф, який  мав би непарне число непарних  вершин.

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

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

4. Граф з більш ніж  з двома непарними вершинами  неможливо зобразити одним розчерком [36, c. 21-22].

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

2. Основні поняття теорії графів

 

Вище було розглянуто інтуїтивно описане поняття графа. Формалізуємо його.

Нехай V – не порожня множина, V(2) – множина всіх його двоелементних підмножин. Пара (V, E), де E – довільна підмножина множини V(2), називається графом (неорієнтованим графом).

Елементи множини V називаються вершинами. Елементи множини E – ребрами. Отже, граф – довільна множина вершин V і довільний набір E пар вершин, або ребер, причому E ≤ V(2). Множини ребер і вершин графа G позначають символами EG та VG відповідно. Вершини і ребра графа називають його елементами. Число вершин графа G називається його порядком і позначається через | VG | або просто | G |, число ребер позначається | EG |. Якщо | VG |= n, | EG | = m, то G називається (n, m) – графом [33, c.27].

Невпорядкована пара вершин називається ребром, впорядкована – дугою графа.

Граф, який містить тільки ребра називається неорієнтованим. Граф, який містить лише дуги – орієнтованим графом.

Пара вершин може з’єднуватись двома або більше ребрами (дугами одного напрямку), такі ребра (дуги) називаються кратними.

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

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

Вершини, з’єднані ребром або  дугою, називаються суміжними. Ребра, які мають спільну вершину, теж називають суміжними. Ребро (дуга) і будь-яка з його двох вершин називаються інцидент ними. Говорять, що ребро (u, v) з’єднує вершини u і v, а дуга (u, v) починається в вершині u і закінчується в вершині v.

 Множина всіх вершин  графа G, суміжних з деякою вершиною v, називається оточенням вершини v і позначається або NG(v)  або N(v).

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

В ролі ілюстрації розглянемо граф G, зображений на рис. 1.3.

Рис.1.3.

Це (6,7) – граф, VG = {1,2,3,4,5,6}, EG = {{1,2}, {2,3}, {3,6}, {3,5}, {2,6}, {2,5}, {2,4}, {6,4}}. Вершини 1, 2 – суміжні, а 1, 3 – не суміжні. Вершина 4 і ребро {2,4} – інцидентні. N(2) = {1,2,3,4,5,6}, N(5) = {2,3,6} – оточення вершин 2 і 5 [20, c.43].

Граф G називається повним, якщо будь-які дві вершини графа суміжні.

Повний граф порядку n позначається символом Kn, число ребер в ньому рівне α. На рис.1.4. зображені графи Kn для n ≤ 5.

Рис. 1.4.

Граф називається порожнім, якщо в ньому немає ребер. Порожній граф порядку n позначається через Оn (рис.1.5, а).

Цикл –це замкнений ланцюг. Ланцюг – лінія на графі, що не проходить ні по якому ребрі графа більше одного разу.

На рис.1.5,б показані прості цикли Сn (n=3,4), на рис.1.5.(в) – прості ланцюги Рn (n = 2,3,4).

Рис.1.5.

Очевидно, що К2 = Р2, а К3 = С3. На рис.1.6. показано два зображення простого циклу С5.

Рис.1.6.

На рис.1.7. зображено колеса Wn (n = 3,4,5).

Зазначимо, що W3  = K4 і |W| = n + 1.

Рис.1.7.

На рис.1.8. зображений граф Петерсена.

Рис.1.8.

Далі в роботі неодноразово будуть використовуватись поняття  «розбиття» та «покриття».

Набір підмножини S називається покриттям множини S, якщо об’єднання цих підмножин співпадає з S.

Покриття називають розбиттям, якщо ніякі дві підмножини, що входять в нього, не перетинаються [8, c.56-57].

Граф називається дводольним, якщо існує таке розбиття множин його вершин на дві частини (долі), що кінці кожного ребра належать різним частинам. Якщо при цьому будь-які дві вершини, які входять в різні долі, суміжні, то граф називається повним дводольним. Повний дводольний граф , долі якого складаються із p і q вершин, позначається символом К_р,q.

При р=1 отримуємо зірку К_1,q.

Очевидно, що К_1,1 =К₂=Р₂, К_1,2=Р₃, К_2,2=С₄. Зазначимо, що одна з долей дводольного графа може бути пустою.

Так О₁ – дводольний граф з однією пустою долею, О₂ можна трактувати як дводольний граф з двома одновершинними долями, або як дводольний граф, одна з долей якого містить дві вершини, а друга є пустою множиною.

На рис.1.9. зображено зірку К_1,6, повний дводольний граф К_3,3, дводольний граф К_2,3.

                  K_1,6                                    K_3,3                                     K_2,3

Рис.1.9.

Аналогічно дводольним визначають k-дольний і повний  k-дольний графи для k=3,4,… .На рис.1.10 зображено трьохдольний граф.

Рис.1.10

Два графа G(V,E) i H(W,I) називаються ізоморфними, якщо існує взаємно-однозначна відповідність між множинами V,W і множинами ребер E,I, яка зберігає відношення інцидентності [6, c.28].

Наприклад, три графи зображені  на рис. 1.11. ізоморфні, а графи, зображені  на рис.1.12. – не ізоморфні.

Рис.1.11.

 

Рис.1.12

Іноді наведене вище поняття  графа є недостатнім і доволиться розглядати більш загальні об’єкти, в яких дві вершини можуть з’єднуватись більш ніж одним ребром. Так  виникає поняття «мультограф». Мультограф – це пара (V,E), де V – непорожня множина (вершин), а E – сімейство підмножини множини Е (ребер). Використання терміну «сімейство» замість множини означає, що елементи множини Е можуть повторюватись, тобто допускаються кратні ребра.

Подальше узагальнення полягає  в тому, що окрім кратних ребер  допускаються ще петлі, тобто ребра, що з’єднують вершину саму з собою. Псевдограф – це пара  (V,E), де V – не порожня множина (вершин), а E – деяке сімейство невпорядкованих пар  вершин (ребер), не обов’язково різних. На рис. 1.13.(а) зображено мультограф, а на рис.1.13.(б) – псевдо граф.

Рис.1.13.

Визначаються також і  орієнтовані графи. Орієнтований граф (орграф) – це пара (V,A), де V – множина вершин, А – множина орієнтованих ребер, які називаються дугами. Якщо а=(v₁, v₂) – дуга, то вершини v₁ і v₂ називаються її початком і кінцем відповідно. На рисунку дуги помічаються стрілками, що вказують напрям від початку до кінця (рис.1.14(а)). Аналогічно визначається орієнтований мультограф (рис.1.14(б)).

Рис.1.14.

Розглядаються також графи, у яких є дуги, і неорієнтовані  ребра.

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

1.2. Основні способи  задання графів

 

Існує декілька способів задання  графів.

Одним зі способів задання  графа G =(V,E ) є задання кожної з множин V і E за допомогою переліку їх елементів.

Приклад 1. Граф G₁=(V₁, E₁), V₁={v₁,v₂,v₃,v₄} і E₁={(v₁,v₃), (v₁,v₄),(v₂,v₃),(v₂,v₄),(v₃,v₄)} - це граф із чотирма вершинами і п’ятьма ребрами.

А граф G₂=(V₂,E₂), V₂={v₁,v₂,v₃,v₄,v₅} і E₂={(v₁,v₂),(v₂,v₄),(v₁,v₅), (v₃,v₂),(v₃,v₅),(v₄,v₁),(v₅,v₄)} - граф із п’ятьма вершинами і сімома ребрами.

Граф G =(V,E ) зручно зображати за допомогою рисунка на площині, який називають діаграмою графа G. Вершинам графа G ставляться у бієктивну відповідність точки площини; точки, що відповідають вершинам v i w, з’єднуються лінією (відрізком або кривою) тоді і тільки тоді, коли v i w суміжні вершини. Зрозуміло, що діаграма графа змінюватиме свій вигляд у залежності від вибору відповідних точок на площині.

Приклад 2. На рис.1.15. зображені діаграми графів G₁ i G₂ з попереднього прикладу.

Рис. 1.15.

Графи можна задавати також  за допомогою матриць.

 

1.2.1. Задання графа  за допомогою матриці інцидентності  та списку ребер

 

Задати граф означає задати для нього множину вершин і  ребер, а також відношення інцидентності. Коли граф G – скінчений, для опису його вершин і ребер достатньо їх занумерувати. Нехай v1, v2, …, vn – вершини графа G;            е1, е2, … , еn – його ребра. Відношення інцидентностві можна означити матрицею | E | = || ε_ij ||,  що має m рядків і n стовпців. Стовпці відповідають вершинам графа, а рядки – його ребрам. Якщо ребро еі є інцидентним вершині v_j,  то ε_ij = 0. Це – матриця інцидентності графа G, яка є одним із способів його визначення для графа, заданого на рис.1.15 [36, c.180-182].

У матриці інцидентності || ε_ij || орієнтованого графа G, якщо v_j – початок ребра е_i, то ε_ij = -1; якщо v_j – кінець е_i, то ε_ij = 1; якщо е_i – петля, а v_j – інцидентна їй вершина, то ε_ij = α, де α – будь-яке число, відмінне від 0, 1 та -1, в інших випадках ε_ij = 0.

Матриця інцидентності  для графа, зображеного на рис.1.16 .             Таблиця 1

	v1	v2	v3	v4	v5	v6	v7
e1	1	1	0	0	0	0	0
e2	1	0	1	0	0	0	0
e3	0	1	0	1	0	0	0
e4	1	0	0	0	1	0	0
e5	0	1	0	0	0	1	0
e6	0	0	1	1	0	0	0
e7	0	0	1	0	1	0	0
e8	0	0	0	1	0	1	0
e9	0	0	0	0	1	0	1
e10	0	0	0	0	0	1	1
e11	0	0	0	0	1	1	0