Материал: discrete_mathematics

Доповненням графа G = (V, E) називають граф

G = (V, V (2) \ E).

Отже, граф G має ту саму множину вершин V, що й граф G, а вершини графа G суміжні тоді й лише тоді, коли вони несуміжні в G. Для графа G із n вершинами виконується G = Kn \ G.

Графи G1 i G2 ізоморфні тоді й тільки тоді, коли ізоморфні їхні доповнення G1 i G2 .

Приклад 4.8. Об'єднання й перетин графів H1 і H2 із прикладу 4.6 подано на рис. 4.4, а доповнення графів G2 i H2 – на рис. 4.5.

Граф G, ізоморфний своєму доповненню G, називають са

модоповнювальним.

Приклад 4.9.

1. Граф G = (V, E), у якому

V = {a, b, c, d} і E = {(a, b), (b, c), (c, d)},

самодоповнювальний.

2. Чому дорівнює кількість ребер у графі G, якщо граф G має

n вершин і k ребер?

n(n – 1)/2 – k (див. приклад 4.7(1)).

3.Визначити, скільки існує попарно неізоморфних графів, які мають 8 вершин і 25 ребер.

Доповнення кожного з таких графів матиме 8 вершин і 3 ребра (див. попередній пункт). Існує тільки 5 попарно неізоморфних графів з такими параметрами. Доповнення кожного із цих п'яти графів задовольняють умову задачі.

4.Довести, що кількість вершин будь-якого само доповню-

вального графа дорівнює або 4k, або 4k + 1, k N.

167

Якщо m – кількість ребер самодоповнювального графа G = (V, E) з n вершинами, то n(n – 1)/2 – m = m, тобто

n(n – 1) = 4m.

Із того, що число n(n – 1) кратне 4, випливає, що n = 4k або n = 4k + 1, k N. ◄

Завдання для самостійної роботи

1. Накресліть діаграму повного графа з n вершинами Kn для: (а) n = 2; (б) n = 3; (в) n = 4; (г) n = 5.

2. Чи існує повний граф, у якого кількість ребер дорівнює: (а) 21; (б) 27; (в) 500…0500…0 (у кожній групі k нулів); (г) 8k 2 + 2k, k N?

3.Довести, що для довільного графа G об'єднання G G є повним графом.

4.Нехай графи G1 = (V, E1) i G2 = (V, E2) задано за допомогою матриць суміжності A1 та A2, відповідно (|V | = n). Визначити матрицю суміжності A для графа:

5. Довести, що ізоморфне відображення ϕ графа G1 = (V1, E1) на граф G2 = (V2, E2) установлює певне взаємно однозначне відображення ψ множини ребер E1 на множину ребер E2.

6.Довести, що ізоморфні графи мають однакову кількість вершин та однакову кількість ребер.

7.Довести, що графи ізоморфні тоді й тільки тоді, коли ізоморфні їхні доповнення.

8.Визначити, скільки існує попарно неізоморфних графів, які мають:

(а) 8 вершин і 26 ребер; (б) 5 вершин і 78 ребер; (в) 6 вершин і 12 ребер.

9.Знайти нетривіальний самодоповнювальний граф із найменшою кількістю вершин.

10.Довести, що довільний самодоповнювальний граф містить або 4k 2 − k, або 4k 2 + k ребер, k N.

168

4.3. Графи та бінарні відношення

Між множиною всіх графів із множиною вершин V і множиною всіх антирефлексивних симетричних бінарних відношень на V існує взаємно однозначна відповідність: графу G = (V, E) відповідає таке відношення R на V, що (v, w) R тоді й тільки тоді, коли (v, w) E, v, w V. Зокрема, порожньому графу G = (V, ) відповідає порожнє відношення на V (R = ), а повному графу − відношення (V V) \ iV, де iV – діагональне (тотожне) відношення: iV = {(v, v) | v V }.

Очевидно, що операціям об'єднання, перетину й доповнення графів відповідають аналогічні операції для відношень. Якщо графам G1 i G2 відповідають відношення R1 i R2, то гра-

фам G1 G2, G1 ∩ G2 і G1 – відношення R1 R2, R1 ∩ R2 i

R1 \ iV = (V V) \ (R1 iV).

Якщо R – транзитивне відношення, то у відповідному графі G для кожної пари ребер (v, w), (w, u) E існує замикальне ребро

(v, u) E.

4.4. Степені вершин графа

Степенем δ(v) вершини v називають кількість інцидентних їй ребер. Вершину степеня 0 називають ізольованою, а вершину степеня 1 − кінцевою (або висячою).

Кубічним називають граф, степені всіх вершин якого дорівнюють 3.

У будь-якому графі G = (V, E) виконується рівність

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

Приклад 4.10.

1. Як визначити степінь певної вершини графа G за його матрицею суміжності A?

169

Степінь вершини v із номером i дорівнює сумі елементів i-го рядка матриці A, оскільки ця сума визначає кількість вершин, суміжних із вершиною v.

2. Нехай A − матриця суміжності графа G із n вершинами. Довести, що i-й діагональний елемент матриці A2 дорівнює степеню δ(vi) i-ї вершини графа G, i = 1, 2, …, n.

Елемент аіі(2) матриці A2

аіі(2) = ∑aik aki = ∑aik2 = ∑aik , k k k

оскільки aik = aki і aij{0, 1}.

Отже, аіі(2) = δ(vi) (див. попередню задачу).

3. Довести, що в будь-якому графі з n вершинами (n ≥ 2) завжди знайдуться принаймні дві вершини з однаковими степенями.

Припустимо, що існує граф G із n вершинами, усі степені вершин якого попарно різні. Ці степені можуть дорівнювати 0, 1, 2, ..., n – 1. Однак якщо в графі G є вершина степеня 0 (ізольована), то в ньому не може бути вершини степеня n – 1. Отже, степені принаймні двох вершин збігаються.

4. Визначити, чи існує граф із шістьма вершинами, степені

(а) Такий граф не існує, тому що сума степенів усіх його вершин непарна, що суперечить рівності (4.1).

(б) Такий граф існує, його матриця суміжності

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

5. Довести, що доповнення жодного кубічного графа не є кубічним графом.

170

Припустимо, що такий кубічний граф G із n вершинами існує. Тоді із того, що степені всіх вершин графа G і його доповнення дорівнюють 3, випливає, що (n – 1) – 3 = 3, тобто n = 7. Звідси

∑ іδ(vі ) = 2 7 = 21,

що суперечить рівності (4.1). ◄

Завдання для самостійної роботи

1.Чому дорівнює степінь кожної вершини у повному графі з n вершинами?

2.Як визначити степінь певної вершини графа G за його матрицею інцидентності B?

3.Скільки вершин має бути в кубічному графі? Скільки ребер

утакому графі?

4.У графі з n вершинами тільки дві вершини мають однакові степені. Чи можуть обидві ці вершини мати степінь 0 або степінь n – 1?

5.У футбольному турнірі беруть участь 15 команд. Довести, що в будь-який момент знайдеться команда, яка зіграла парну кількість матчів.

6.Довести, що в ізоморфних графів кількість вершин степеня k однакова для довільного k.

7.Визначити, чи існує граф із шістьма вершинами, степені яких дорівнюють:

4.5. Шлях у графі. Зв'язність графів

Маршрутом (або шляхом) у графі G = (V, E) називають послідовність

вершин vi і ребер ei таку, що кожні два сусідні ребра в ній мають спільну вершину, отже, ei = (vi, vi + 1), i = 1, 2, …, k. Вершину v1 називають початком, а вершину vk + 1 − кінцем шляху. Усі інші вершини цього шляху називають проміжними, або внутрішніми.

171