Цикломатичне число графа

Означення. Нехай G(V, E) скінченний неорієнтований граф. Його цикломатичним числом називається число

(G) = n_(G) + m(G) – n(G),

де n_(G) – кількість зв’язних компонент графа; m(G) – кількість його ребер, а n(G) – кількість вершин.

Цикломатичне число дерева дорівнює нулю.

Бінарним (орієнтованим) деревом називається дерево, яке задовольняє умови:

а) в кореневу вершину не входить жодна дуга;

б) будь-яка інша вершина має точно одну вхідну дугу і тільки або дві, або жодної вихідної дуги.

Наприклад, це дерево має чотири внутрішні вершини і 5 листків. Внутрішні вершини позначено кругами, листки – прямокутниками.

Розглянемо всі різні бінарні древа з точно трьома внутрішніми вершинами.

Має місце таке твердження.

Твердження. Кількість різних бінарних дерев з n внутрішніми вершинами дорівнює .

Доведення. Позначимо шукану кількість d_n, вважаючи d₀ = 1. Для довільного n₀ > 0 число d_n дорівнює кількості способів розміщення одного бінарного дерева з k внутрішніми вершинами зліва від кореня і іншого бінарного дерева з n – k – 1 вершинами справа від кореня.

k

n – k – 1

Тоді d_n = d₀d_{n – 1} + d₁d_{n – 2} + … + d_{n – 1}d₀ = .

Введемо поліномну твірну функцію

F(x) = .

Піднісши до квадрату, маємо

F²(x) = = .

Оскільки d_{k + 1} = , то

F²(x) = = .

Отже

F²(x) = (F(x) – 1).

Розв’язуючи це рівняння, знаходимо

F(x) = .

Враховуючи, що F(0) = = d₀ = 1, вибираємо значення

F(x) = ,

оскільки F(x) = = 1.

Розвинемо функцію в ряд Маклорена. Маємо

(1 – 4x)^1/2 = 1 + .

Використовуючи цей розклад, одержуємо

F(x) = =

= =

= .

Отже,

d_n = (–1)ⁿ = (–1)ⁿ =

= (–1)²ⁿ = = = .

Значення виразу при n = 0, 1, 2, … називається числами Каталана.

Означення. Кістяковим деревом зв’язного графа G називається будь-яка його частина, що містить усі вершини графа G і є деревом.

Покажемо існування кістякового дерева для довільного зв’язного псевдографа G(V, X), описавши алгоритм його вибору.

Він включає такі кроки:

1. Вважаємо, що i = 1. Вибираємо в G довільну вершину v₁, що утворює підграф G₁ псевдографа G, який є деревом.

2. Якщо i = n, де n = n(G), то задачу розв’язано і G_i – шукане кістякове дерево псевдографа G. В іншому випадку переходимо до пункту 3.

3. Нехай вже побудовано дерево G_i, що є підграфом псевдографа G і містить деякі вершини v₁, …, v_i, 1  i  n – 1. Будуємо граф G_{i + 1}, додаючи до графа G_i нову вершину v_{i + 1}  V, суміжну в G з деякою вершиною v_j графа G_i,та нове ребро, інцидентне вершинам v_i і v_{i + 1}. Очевидно, граф G_{i + 1} є деревом. Прирівнюємо i:= i + 1 і переходимо до пункту 2.

Означення. Граф G(V, E) називається зваженим, якщо на множині його ребер означено вагову функцію l: E  R, тобто кожному ребру e  E зв’язного графа G = {V, E} з непорожньою множиною ребер E поставлено у відповідність величину l(e) – вагу ребра e.

Означення. Нехай G – звичайний граф. Граф G називається k-розфарбуванням, якщо існує таке розкладання множини його вершин V на k неперерізних класів V₁, …, V_k, що

V = , E(V_i) E(V_j) =   i, j. (2)

Найменша кількість (G) класів у можливому розфарбуванні (2) називається хроматичним числом графа, а сам граф – -хроматичним.

Означення. Цикли, що містять усі ребра графа, називаються ейлеровими, а графи, які мають цей цикл, – ейлеровими графами.

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

Ейлеровим називається ланцюг, що включає всі ребра заданого скінченного неорієнтованого графа G, але має різні початок і кінець.

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