и простих ланцюгів і простих циклів наведені на ріс.1.14:
(1,3), (3,4), (4,6) - простий ланцюг;
(1,2), (2,5), (5,6) - простий ланцюг;
(1,3), (3,4), (4,6), (6,5), (5,2) (2,1) - простий цикл.
Рис 1.14. Приклад графа з простими ланцюгами і простими циклами
Визначення 1.9.
Граф є подграфом графа, якщо. Якщо, то підграф називається остовно подграфом.
Визначення 1.10.
Граф є сумою графів, якщо
ця сума називається прямої, якщо,.
1.3 Оцінки для числа ребер з компонентами пов'язаності
Визначення 1.11.
Граф називається зв'язаним, якщо будь-які вершини і сполучені ланцюгом з початком в і кінцем в. З симетрії випливає, що в цьому випадку і вершина з'єднана з вершиною.
Теорема 1.2.
Кожен граф є прямою сумою зв'язкових графів.
Доказ. На множині вершин граф визначимо ставлення, якщо поєднується з. Ставлення є відношенням еквівалентності. Позначимо через. Тоді й є розбиття на класи еквівалентності. Графи є пов'язаними графами і
(1.2)
є прямою сумою зв'язкових графів. Теорема доведена.
Ці графи називаються компонентами зв'язності.
Розглянемо оцінки для числа ребер з компонентами зв'язності.
Теорема 1.3.
Нехай граф, який складається з вершин, ребер і компонент пов'язаності. Тоді виконуються нерівності
(1.3)
Доказ. Доведемо спочатку нерівність. Будемо доводити індукцією по числу ребер. Припустимо, що нерівність справедливо для всіх графів з кількістю ребер. Нехай граф з вершин, ребер і компонентами зв'язності. Викреслимо максимальне можливе число ребер так, щоб не змінювалося число компонент зв'язності. Число ребер в отриманому графі позначимо.
Розглянемо для прикладу граф, зображений на малюнку (1.15)
Рис. 1.15. Приклад 1 графа для оцінки зв'язності
У ньому .Вичеркнув два ребра, отримаємо граф. Викреслити далі якесь ребро, не порушуючи зв'язаність, вже не можна (див. Ріс.1.16)
Рис. 1.16. Приклад 1 графа для оцінки зв'язності
Повернемося до графу, отриманого з. Викресливши в ньому ще одне ребро, ми отримаємо граф з числом компонент зв'язності на одиницю більше. В силу індуктивного припущення, справедливого, бо маємо,, звідки.
Для доказу верхньої оцінки у нерівності (1.3) замінимо кожну компоненту повним графом. Нехай і два повних, отриманих з компонент зв'язності і, а і число ребер в цих компонентах. Замінимо на повний граф, додавши одну вершину, а замінимо на повний граф, віднявши одну вершину. Тоді загальне число вершини не зміниться, а число ребер збільшиться на позитивну величину
Отже, для того, щоб число ребер в графі було максимально можливим (при фіксованих і), граф повинен складатися з ізольованих вершин і повного графа з вершинами. Звідси і випливає нерівність (1.3). Теорема доведена.
З нерівності (1.3) випливає таке слідство.
Слідство. Будь граф з і більше ніж ребрами є зв'язковим.
Дійсно, якщо граф з вершинами має два компоненти зв'язності, то максимальне число ребер не перевищує.
Знайти компоненти сильної зв'язності графа на ріс.1.17.
Відповіді
Ріс.1.17. 7-ми вершинний граф для обчислення компонентів зв'язності.
1.4 Орієнтовані графи, графи, з петлями, графи з паралельними дугами
Дамо визначення орієнтованих графів, графів з петлями і графів з паралельним дугами.
Неформально, граф виглядає як діаграма, є безліч точок площини (вершин або вузлів), з'єднаних між собою лініями (ребрами). Діаграма дає уявлення про зв'язки між елементами (вершинами), але нічого не говорить про метричних властивостях (довжина ліній, їх форма і т.д.).
В залежності від типу ребер відрізняються кілька типів графів. Петля - це ребро, що з'єднує вершину саму з собою. У мультиграфом петлі не допускаються, але пари вершин можуть з'єднуватися декількома ребрами, які називаються кратними, або паралельними. У псевдографів допускаються петлі і кратні ребра.
У звичайному графі немає ні петель, ні кратних ребер.С допомогою графів подаються структурні залежності між елементами, відповідний граф називається орієнтованим, або Орграф, а його орієнтовані ребра - дугами. Граф, який складається з орієнтованих і неорієнтованих ребер одночасно, називається змішаним.
Ріс.1.18. Види орієнтованих графів
Визначення 1.12.
Нехай множина вершин, - множина впорядкованих пар елементів з (будемо називати їх дугами). Орієнтованім графом називатимемо пару множин, де.
Дуга називається дугою з в (див. ріс.1.19). ...
