Материал: discrete_mathematics

Припустимо, що такий кубічний граф 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

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

(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