Материал: discrete_mathematics

Розділ 4 ТЕОРІЯГРАФІВ

Роком виникнення теорії графів вважають 1736, коли Леонард Ейлер опублікував розв'язання задачі про кенігсберзькі мости, а також знайшов загальний критерій існування ейлерового циклу в графі (див. п. 4.10). Картинка у вигляді набору точок на площині та ліній, проведених між деякими з них, стала зручною й наочною формою зображення найрізноманітніших об'єктів, процесів і явищ (див. п. 4.12). Нині теорія графів – важливий розділ дискретної математики.

4.1. Поняття графа. Способи задання графів

Нехай V – непорожня скінченна множина, а V (2) – множина всіх двохелементних підмножин (невпорядкованих пар різних елементів) множини V.

Графом (неорієнтованим графом) G називають пару множин

(V, E), де E − довільна підмножина множини V (2) (E V (2)); позначають G = (V, E).

Елементи множини V називають вершинами графа G, а елементи множини E − його ребрами. Відповідно V називають

множиною вершин, а E − множиною ребер графа G.

Традиційно ребра {v,w} записують за допомогою круглих дужок (v, w) (іноді просто vw).

Граф, що складається з однієї вершини, називають тривіаль ним, а граф G = (V, ) – порожнім.

Нехай задано граф G = (V, E). Якщо (v, w) Е, то кажуть, що

вершини v i w суміжні, інакше вершини v i w несуміжні. Якщо

е = (v, w) − ребро графа, то вершини v i w називають кінцями ребра е. У цьому разі кажуть також, що ребро е з'єднує вершини v i w. Вершину v і ребро е називають інцидентними, якщо v – кінець ребра е. Два ребра називають суміжними, якщо вони мають спільну вершину.

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

Один із них – задати кожну із множин V та E за допомогою переліку їхніх елементів.

Приклад 4.1. G1 = (V1, E1), де V1 = {v1, v2, v3, v4} і E1 = {(v1, v3),

(v1, v4), (v2, v3), (v2, v4), (v3, v4)} − граф із чотирма вершинами й п'ятьма ребрами, а G2 = (V2, E2), де

V2 = {v1, v2, v3, v4, v5} і

E2 = {(v1, v2), (v2, v4), (v1, v5), (v3, v2), (v3, v5), (v4, v1), (v5, v4)} −

граф із п'ятьма вершинами й сімома ребрами. ◄

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

Приклад 4.2. На рис. 4.1 подано діаграми графів G1 i G2 із по-

Графи можна задавати також за допомогою матриць. Занумеруємо всі вершини графа G натуральними числами від

1 до n. Матрицею суміжності A графа G називають квадратну n n-матрицю, у якій елемент aij i-го рядка та j-го стовпця дорівнює 1, якщо вершини vi та vj з номерами i та j суміжні, і дорівнює 0 в іншому випадку.

Приклад 4.3. Для графів G1 i G2 маємо відповідно

Очевидно, що матриці суміжності графів симетричні. Занумеруємо всі вершини графа G числами від 1 до n, а всі

його ребра − числами від 1 до m. Матрицею інцидентності B

162

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

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

Операція вилучення ребра e з графа G = (V, E) − це вилучення елемента e змножини E. Прицьому всі вершинизберігаються.

Графи G1 = (V1, E1) і G2 = (V2, E2) називають ізоморфними, якщо існує таке взаємно однозначне відображення ϕ множини

вершин V1 на множину вершин V2, що ребро (v, w) E1 тоді й тільки тоді, коли ребро (ϕ(v), ϕ(w)) E2.

Відображення ϕ називають ізоморфним відображенням, або

ізоморфізмом, графа G1 на граф G2.

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

Приклад 4.6. Неважко переконатися, що всі графи на рис. 4.2, ізоморфні між собою, а графи на рис. 4.3 − не ізоморфні.

H1 H2 Рис. 4.3 ◄

165