Властивості графів

Маршрути, цикли, зв’язність

Число K ребер маршруту називається довжиною цього маршруту.

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

Циклом, називається циклічний ланцюг, а простим циклом - простий циклічний ланцюг.

Граф називається антициклічним, або лісом, якщо в ньому відсутні цикли. Безпосередньо з означення маршруту і циклу випливають такі твердження:

• будь-який маршрут, котрий з’єднує дві вершини графа, має простий ланцюг, що з’єднує ці вершини;

• будь-який цикл в графі завжди має простий цикл.

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

Граф зв’язний тоді і лише тоді, коли його не можна представити у вигляді диз’юнктивного об’єднання двох графів. Максимальний зв’язний підграф називається компонентом зв’язності.

Властивості регулярних графів

Властивості двочастинних та зв’язних графів

Існує простий критерій двочастинності графа, який виражається в термінах довжини циклів. Граф G = (V, Е) є двочастинним тоді і лише тоді, коли він не має циклів непарної довжини.

Визначаючи спосіб розпізнавання двочастинності графа, будемо приписувати номери 0 та 1 вершинам графа G:

• починаючи з довільної вершину u графа G, приписуємо їй номер 0;

• кожній вершині з множини Cm(u) приписуємо номер 1;

• для всіх вершин, суміжних з вершинами множини Cm(u) приписуємо номер 0;

• для всіх вершин, яким приписали номер 0, знаходимо всі суміжні з ними вершини і приписуємо їм номер 1 і т. д.

Визначимо тепер одну з властивостей зв’язних графів.

Якщо граф G - граф з п вершинами і k компонентами зв’язності, то число його ребер задовольняє нерівності

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

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

Метричні характеристики зв’язних графів

Нехай G = (V, Е) - зв’язний граф, a u і v - дві його різні вершини. Відстанню між вершинами u і v називається довжина найкоротшого маршруту, який з’єднує вершини u і V, і позначається d(u, v). Покладемо також, що d (u, н) = 0. Очевидно, що для введеної таким чином відстані виконуються аксіоми:

1. d(u, v) ≥ 0;

2. d(u, v) =0 тоді і лише тоді, коли u = v;

3. d(u, v) = d(u, v);

4. d(u, v) + d(u, w) ≥ d(u, w) (нерівність трикутника).

Поняття відстані між вершинами дає можливість визначити поняття степеня графа. Нехай G - зв’язний граф, к - натуральне число. Граф G^k - к-й степінь графа G, має ту ж множину вершин, що й G, а нерівні між собою вершини u і V суміжні в графі G^k тоді і лише тоді, коли d(u, v) ≤ к. Безпосередньо з цього випливає така властивість графа G^k.

Якщо k ≥ ∣V∣ -1, де V - множина вершин графа G, то G^k - повний граф.

Нехай u - деяка фіксована вершина графа G = (V, Е). Величина e(u) = max d(u, v), V ∈ V, називається ексцентриситетом вершини н. Максимальний серед всіх ексцентриситетів вершин графа G називається діаметром графа G і позначається d(G). Отже, d(G) = max e(u), u ∈ V.

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

У графі G (рис. 14) маємо d(l, 2) = 1, d(l, 3) = 2 = d(l, 5), е(1) = 2,

Властивості ейлерових та гамільтонових графів

Одним з важливіших різновидів зв’язних графів є ейлерові та гамільтонові графи.

Зв’язний граф G називається ейлеровим (рис. 47), якщо існує замкнутий ланцюг, який включає кожне його ребро. Такий ланцюг називається ейлеровим ланцюгом.

Зв’язний граф G називається напівейлеровим (рис. 15), якщо в

ньому існує ланцюг, який включає кожне його ребро. Таким чином, всякий ейлерів граф буде напівейлеровим.

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

Нехай G = (V, Е) - ейлерів граф. Тоді наступна процедура завжди можлива і веде до ейлерового ланцюга в графі G: виходячи з будь-якої вершини u ∈ V, йдемо по ребрах графа G довільним чином згідно з такими правилами:

1. стираємо ребра, які пройдені, і стираємо ізольовані вершини, які при цьому виникають;

2. на кожному етапі йдемо по мосту лише тоді, коли немає інших можливостей.

Проблема існування замкнутого ланцюга, який проходить через кожне ребро зв’язного графа G, аналогічно може бути сформульована і для вершин. Тобто, чи існує замкнутий ланцюг у зв’язному графі G, який проходить рівно один раз через кожну вершину графа G. Очевидно, що такий ланцюг має бути циклом. Якщо такий цикл у графа G існує, то він називається гамільтоновим ланцюгом, а граф G - гамільтоновим графом.

Якщо в графі G = (V, Е) порядку п зафіксувати одну з вершин і обхід графа завжди починати з неї, то всякому гамільтоновому циклу буде відповідати перестановка елементів множини V.

2.6.4.