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

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

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

Нехай граф, який складається з вершин, ребер і компонент зв язності. Тоді виконуються нерівності

Доведення . Доведемо спочатку нерівність .Будемо доводити індукцією за числом ребер. Припустимо, що нерівність справедлива для всіх графів з числом ребер .Нехай граф з вершин, ребер і

компонентами зв’язності.Викреслимо максимальне можливе число ребер так, щобне змінювалося число компонент зв’язностя.Число ребер в отриманому графі позначемо .