Основи теорії графів. Властивості ойлерових та гамільтонових графів (стр. 2 из 8)

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

Означення 1.6.

Якщо

, то вершина називається кінцевою вершиною графа . Якщо , то вершини називається ізольованою(див рис. 1.11)

Рис.1.11. Визначення кінцевих та ізольованих вершин графа

1.2 Лема про рукостискання

Формулювання цієї леми просте – „кількість рук, що приймають участь у рукостисканні N-пар людей, дорівнює 2*N”. Лему можна представити у формі графу, де N вершин з’єднані ребрами d(x_i,x_j) рукостискання 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 графу для оцінки зв’язності