Курсовая работа: Основи теорії графів. Властивості ойлерових та гамільтонових графів

Число усіх різних графів з вершинами дорівнює (табл.1.1):

Доведення. Справді, граф повністю визначено, якщо вказано множину , яка є підмножиною . Множина містить елементів, тому число усіх її підмножин дорівнює .

Таблиця 1.1

Зображення повних графів з кількістю вершин від 5 до 11 [3]

Означення 1.4.

Вершини та графа інцидентні, якщо .

Означення 1.5.

Степенем вершини графа називається число вершин , які інцидентні вершині ( число відрізків які виходять з вершини ) – див.рис.1.10.

Рис.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-х вершинного графу