Материал: discrete_mathematics

Один із них – задати кожну із множин 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

Наприклад, відображення ϕ множини вершин

V1 = {1,2,3,4,5,6}

графа G1 на множину вершин

V2 = {a, b, c, d, e, f}

графа G2, за яким ϕ(1) = a, ϕ(2) = c, ϕ(3) = e, ϕ(4) = f, ϕ(5) = d, ϕ(6) = b, є ізоморфізмом графа G1 на граф G2. Аналогічно можна побудувати ізоморфне відображення графа G2 на граф G3.

Відношення ізоморфізму є відношенням еквівалентності на сукупності графів.

Граф G = (V, E) називають повним, якщо будь-які дві його вершини суміжні (тобто E = V (2)). Повний граф із n вершинами позначають Kn.

Приклад 4.7.

1. Скільки ребер містить повний граф із n вершинами? Оскільки в повному графі будь-які дві його вершини з'єднані

ребром, то кількість його ребер становить C(n, 2) = n(n – 1)/2. 2. Чи існує повний граф, у якого кількість ребер дорівнює: (а) 15; (б) 18; (в) 199…900…0 (k дев'яток і k нулів)?

(а) Кількість ребер повного графа з n вершинами дорівнює n(n – 1)/2. Рівняння n(n – 1)/2 = 15 має корені 6 і –5. Отже, існує повний граф із6 вершинами, кількість реберу якому дорівнює 15.

(б) Рівняння n(n – 1)/2 = 18 не має натуральних коренів, тому такий повний граф не існує.

(в) Розглянемо рівняння

n(n – 1) = 2 199…900…0 = 200…0 199…9 (k нулів і k дев'яток).

Число у правій частині цього рівняння можна подати у вигляді 2 10k(2 10k – 1), тобто n = 2 10k. Отже, такий повний граф існує й має 2 10k вершин. ◄

Для графів можна означити операції об'єднання, перетину й доповнення.

Об'єднанням графів G1 = (V1, E1) і G2 = (V2, E2) називають

граф G = (V1 V2, E1 E2); позначають G = G1 G2. Об'єднання G = G1 G2 називають прямою сумою графів G1 i

G2, якщо V1 ∩ V2 = .

Перетином і різницею графів G1 = (V, E1) i G2 = (V, E2) з од-

наковими множинами вершин називають відповідно графи

G′= (V, E1 ∩ E2) i G′′ = (V, E1 \ E2); позначають G′= G1 ∩ G2 і G′′ = G1 \ G2.

166