Материал: discrete_mathematics

Найчастіше маршрут записують лише як послідовність вершин, що входять до його складу, тобто замість послідовності

(4.2) пишуть v1, v2, … , vk + 1.

Кількість k ребер у маршруті називають його довжиною. Кажуть, що цей маршрут з'єднує вершини v1 і vk + 1, або веде із вершини v1 до вершини vk + 1.

Маршрутом довжиною 0 вважають послідовність, що складається з єдиної вершини.

Маршрут, у якому всі ребра попарно різні, називають лан цюгом, а той, у якому всі вершини попарно різні, – простим

ланцюгом.

Маршрут (4.2) називають замкненим (або циклічним), якщо v1 = vk + 1. Замкнений ланцюг називають циклом, а замкнений простий ланцюг − простим циклом.

Граф, усі ребра якого утворюють простий цикл довжиною n, позначаютьCn. Простийциклдовжиною3 називаютьтрикутником.

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

Компонентою зв'язності (або зв'язною компонентою) графа

G називають його зв'язний підграф такий, що не є власним підграфом жодного іншого зв'язного підграфа графа G.

Відстанню між вершинами v і w зв'язного графа (позначають d (v, w)) називають довжину найкоротшого простого ланцюга, що з'єднує вершини v і w.

Оскільки кожна вершина графа G = (V, E) з'єднана сама із собою маршрутом довжиною 0, то для всіх v V виконується рів-

ність d (v, v) = 0.

Ексцентриситетом e(v) довільної вершини v зв'язного графа G = (V, E) називають найбільшу з відстаней між вершиною v і

всіма іншими вершинами графа G, тобто e(v) = max {d(v, w)}.

w V

Діаметром зв'язного графа G (позначають D(G)) називають максимальний зі всіх ексцентриситетів вершин графа G. Мінімальний зі всіх ексцентриситетів вершин зв'язного графа G називають його радіусом і позначають R(G).

Вершину v називають центральною, якщо e(v) = R(G). Центром графа G називається множина всіх його централь-

них вершин.

172

Вершини v i w графа G називаються зв'язаними, якщо в G існує маршрут, що їх з'єднує.

Відношення зв'язаності Z рефлексивне, транзитивне й симетричне, тобто є відношенням еквівалентності на множині V. Розглянемо фактор множину

V /Z = {V1, V2, …, Vt }.

Підграфи Gi = (Vi, Ei), де Ei = E ∩ Vi(2), очевидно, є компонентами зв'язності графа G. Крім того, виконується

G = G1 G2 … Gt.

Цей факт можна сформулювати у вигляді такого твердження. Будь-який граф можна однозначно зобразити у вигляді пря-

мої суми своїх компонент зв'язності.

Якщо граф G зв'язний, то всі його вершини попарно зв'язані, тобто V /Z = {V} i G має єдину зв'язну компоненту, яка збігається із самим графом G.

є циклом, але не є простим циклом. Крім того, граф G є зв'язним і d (1, 6) = 2, d (3, 7) = 3, d (5, 6) = 3, d (3, 4) = 1.

Значення ексцентриситетів вершин цього графа G :

e(1) = 2, e(2) = 2, e(3) = 3, e(4) = 2, e(5) = 3, e(6) = 3, e(7) = 3.

Отже, D(G) = 3 і R(G) = 2. Центром графа G є множина вершин

{1, 2, 4}.

2. Довести, що для будь-якого графа G = (V, E) або він сам, або його доповнення G є зв'язним графом.

Якщо G – зв'язний граф, то твердження справджується. Не-

хай G = (V, E) – незв'язний граф і G1 = (V1, E1) – одна з його компонент зв'язності. Розглянемо графи

G1 i G′ = (V′, E′), де V′= V \ V1 і E′ = E \ E1.

173

Для будь-якої пари вершин v V1 i w V′ у графі G існує ребро (v, w), адже ці вершини несуміжні в графі G. Оскільки для кожної пари вершин v1, v2 V1 графа G1 і довільної вершини w V′ існують ребра (v1, w) i (v2, w), які належать множині ребер графа G , то в графі G такі вершини v1 і v2 зв'язані. Аналогічно встановлюємо зв'язність у графі G будь-якої пари вершин w1 i w2 із мно-

жини V′. Отже, усі пари вершин графа G зв'язані між собою.

3. Довести, що коли G – незв'язний граф, то граф G зв'язний і

D( G ) ≤ 2.

Дійсно, якщо G – незв'язний граф, то з попередньої задачі випливає, що G зв'язний, і для будь-яких двох вершин v та w графа G виконується або d (v, w) = 1, або d (v, w) = 2.

4.Довести, що коли в графі G тільки дві вершини v і w мають непарні степені, тоді ці вершини зв'язані в графі G.

Якщо v і w незв'язані, то вони містяться у різних компонентах

зв'язності G1 і G2. Тоді сума степенів усіх вершин підграфа G1 (або G2) буде непарною, що суперечитиме формулі (4.1).

5.Довести, що самодоповнювальний граф завжди зв'язний. Якщо припустити, що існує незв'язний самодоповнюваль-

ний граф G, то із прикладу 4.11 (2) випливає, що його допов-

нення G – зв'язний граф. А це суперечить умові ізоморфізму

графів G та G . ◄

Доведемо таке важливе твердження щодо зв'язних графів. Нехай G = (V, E) – зв'язний граф і e – деяке його ребро. Розг-

лянемо граф G′, отриманий із G вилученням ребра e.

а) Якщо ребро e належить деякому циклу графа G, то граф G′ зв'язний.

б) Якщо ребро e не належить жодному циклу графа G, то граф G′ незв'язний і має рівно дві компоненти зв'язності.

Доведення. а) Розглянемо дві довільні вершини v і w графа G′. Якщо маршрут M, що з'єднує вершини v і w у зв'язному графі G, не містить ребра e, то він з'єднуватиме вершини v та w також у графі G′. Якщо ж ребро e належить маршруту M і e = (u1, u2), то маршрут, що веде з v у w у графі G′, можна побудувати так:

174

беремо маршрут, що веде з v в u1, додаємо до нього ту частину циклу, що містить ребро e, яка залишилась у графі G′ і з'єднує вершини u1 і u2; відтак завершуємо його маршрутом з u2 у w. Отже, граф G′ зв'язний.

б) Нехай ребро e = (u1, u2) не належить жодному циклу графа G. Тоді в графі G′ вершини u1 та u2 будуть незв'язаними й належатимуть двом різним компонентам зв'язності G1 та G2 графа G′. Крім того, у графі G′ стануть незв'язаними ті й тільки ті вершини, які були з'єднані в графі G маршрутом, що містив ребро e. Отже, кожна вершина v у G′ буде зв'язана або з вершиною u1, або з вершиною u2, тобто v належатиме або G1, або G2. Твердження доведено.

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

1. Спростувати твердження: якщо деякий ланцюг, що веде із вершини v у вершину w, проходить через вершину u (u ≠ v і u ≠ w), то він містить простий ланцюг, що веде з v у w і проходить через u.

2.Довести, що будь-який найкоротший ланцюг, який веде із вершини v у вершину w (v ≠ w), є простим ланцюгом.

3.Довести, що в графі, степені всіх вершин якого більші 1, є цикл.

4.Побудувати граф, центр якого:

(а) складається тільки з однієї вершини; (б) складається тільки із двох вершин;

(в) складається із трьох вершин і не збігається із множиною всіх вершин;

(г) збігається із множиною всіх вершин.

5. Довести, що для довільного графа G виконуються нерівності

R(G) ≤ D(G) ≤ 2R(G).

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

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

175

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

Зв'язність заданого графа G зручно перевіряти за допомогою його матриці суміжності A.

Нехай A − матриця суміжності графа G = (V, E) з n вершинами (|V | = n). Тоді елемент aij(k ) i-го рядка та j-го стовпчика мат-

риці Ak дорівнює кількості шляхів довжиною k, які ведуть у графі G із вершини vi у вершину vj.

Звідси отримаємо такий метод перевірки зв'язності графа G. У графі G вершини vi i vj (i ≠ j) зв'язані тоді й тільки тоді, коли

елемент і-го рядка та j-го стовпчика матриці

A + A2 + A3 + … + An – 1

не дорівнює нулю.

Це випливає із тієї простої властивості, що коли в графі G із n вершинами існує шлях між вершинами vi i vj (i ≠ j), тоді між цими вершинами обов'язково існує шлях довжиною не більше n − 1.

Крім того, щоб вилучити умову i ≠ j для встановлення зв'язності між будь-якими вершинами графа G, можна використову-

вати матрицю

M (n) = In + A + A2 + A3 + … + An – 1,

де In − одинична матриця порядку n (нагадаємо, що будь-яка вершина зв'язана сама із собою шляхом довжиною 0).

Таким чином, граф G зв'язний тоді й тільки тоді, коли в матриці M (n) немає нульових елементів.

Граф G* = (V, E*) називають транзитивним замиканням

графа G = (V, E), якщо (v, w) E*, тоді й тільки тоді, коли вершини v і w зв'язані в графі G.

Отже, транзитивне замикання графа G є повним графом тоді й тільки тоді, коли граф G зв'язний.

Якщо графу G = (V, E) відповідає відношення R на V, то графу G* відповідатиме рефлексивне транзитивне замикання R* відношення R (див. п. 2.6).

Побудуємо для графа G* n × n-матрицю A* за таким правилом: (i, j)-й елемент матриці A* дорівнює 1 тоді й тільки тоді,

176