Основи теорії графів. Властивості ойлерових та гамільтонових графів
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
>
Рис.1.9. Приклад побудови 3-х вершинного графу з різною кількістю ребер (заповнення графу від порожнього до повного)
Природно виникає питання: скільки є різних графів з множиною вершин , якщо . Для цього доведемо наступну теорему.
Теорема 1.1.
Число усіх різних графів з вершинами дорівнює (табл.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(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 графу для оцінки звязності
В ньому .Викресливши два ребра, отримаємо граф . Викреслити далі яке-небудь ребро, не порушуючи зв язності, вже не можна (див.рис.1.16).
Рис. 1.16. Приклад 1 графу для оцінки звязності
Повернемося до графу, отриманого з . Викресливши в ньому ще одне ребро, ми отримаємо граф з числом компонент зв язності на одиницю більшим. В силу індуктивного припущення, справедливого, бо , маємо , звідки .
Для доведення верхньої оцінки в нерівності (1.3) замінимо кожну компо-ненту повним графом. Нехай та два ?/p>