
Рис.1.10. Визначення степенів вершин графу по кількості ребер, що виходять із вершин
Означення 1.6.
Якщо

, то вершина

називається кінцевою вершиною графа

. Якщо

, то вершини

називається ізольованою(див рис. 1.11)

Рис.1.11. Визначення кінцевих та ізольованих вершин графа
1.2 Лема про рукостискання
Формулювання цієї леми просте – „кількість рук, що приймають участь у рукостисканні N-пар людей, дорівнює 2*N”. Лему можна представити у формі графу, де N вершин з’єднані ребрами d(xi,xj) рукостискання i та j – вершин (див. рис.1.12), виконавши наступне доведення.

Рис.1.12. „Лема про рукостискання” 5 осіб у вигляді графу „взаємно-простягнутих рук” (10 пар рук для повної множини рукостискань) [3]
Нехай

граф з множиною верщин

. Тоді

(1.1)
Доведення. Зауважимо,що кожне ребро графа в сумі

враховується двічі (див. рис.1.5), ітому спараведива рівність (1.1).Зауважимо, що сума сту-пенів усіх вершин у графі (або мультіграфі без петель) повинна бути парною. Це випливає з того, що якщо взяти вершини, взагалі не пов'язані одна з одною, то сума ступенів цих вершин дорівнює нулю. Додаючи будь-яке ребро, що пов'язує дві вершини, збільшуємо суму всіх ступенів на 2 одиниці. Таким чи-ном, сума всіх ступенів вершин парна. З рівності 1.1 випливає такє твердження: число вершин непарного степеня в графі

обовязково є парним числом.
Для визначення матриці суміжності, розглянемо граф

. Нехай

Означення 1.7.
Матриця

називається матрицею суміжності ( інцидентності) графа

.
Матриця суміжності

- це симетрична матриця, елементи якої до-рівнюють нулеві або одиниці ( діагональні елементи дорівнюють нулеві) і така, що сума чисел в будь-якому рядку і будь-якому стовпці дорівнює степені від-повідної вершини. Так, для графу, наведеного на рис.1.13, матриця суміжності побудується у вигляді:

Рис.1.13. До побудови матриці суміжності 3-х вершинного графу
Означення 1.8.
Послідовність ребер

, в якій сусідні ребра інцидентні одній і тій же вершині називаються ланцюгом. Ланцюг називається простим, якщо всі вершини, належні йому (крім, можливо, першої і останньої), різні; число в цьому випадку називають довжиною ланцюга.
Якщо

, то ланцюг називається циклом. Цикл, в якому всі вершини різні, називається простим. Приклади простих ланцюгів та простих циклів наведені на рис.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.15)

Рис.1.15. Приклад 1 графу для оцінки зв’язності