- •Лекція №18. Структури та параметри графів
- •Питання для самоперевірки та вправи
- •Лекція №19. Мости, блоки
- •Питання для самоперевірки та вправи
- •Лекція №20. Зв’язність
- •Питання для самоперевірки та вправи
- •Змістовий модуль 5. Спеціальні графи Лекція №21. Двохдольні графи
- •Питання для самоперевірки та вправи
- •Лекція №22. Обходи графів
- •Гамільтонові графи
- •Питання для самоперевірки та вправи
- •Лекція №23. Дерева
- •Питання для самоперевірки та вправи
- •Змістовий модуль 6. Алгоритми на графах Лекція №24. Фарбування графів
- •Деякі числа теорії графів
- •Питання для самоперевірки та вправи
- •Лекція №25 Мережі
- •Розріз мережі
- •Алгоритм знаходження максимального потоку
- •1. Розстановка поміток
- •2. Збільшення потоку
- •Питання для самоперевірки та вправи
- •Питання для самоперевірки та вправи
- •Лекція №27 Побудова дерева найкоротших шляхів. Транспортна задача
- •Питання для самоперевірки та вправи
- •Основна
- •Додаткова
Гамільтонові графи
Якщо в є простий остовний цикл , то називається гамільтоновим графом, а - гамільтоновим циклом. Зараз не відомо ефективних описів гамільтонових графів, але відомо тільки декілька необхідних та декілька достатніх умов існування гамільтонових циклів.
Теорема 22.2 Кожний гамільтонів граф двох-зв’язний.
Теорема 22.3 (теорема Дірака) Якщо в графі для будь-якої вершини ступінь , то граф називається гамільтоновим.
Доведення:
Від супротивного. Нехай - не гамільтоновий граф. Додамо до мінімальну кількість нових вершин , і з’єднаємо їх зі всіма вершинами так, щоб граф , який ми одержимо в результаті, був гамільтоновим.
Нехай - гамільтонів цикл графа , причому , .
Така пара в гамільтоновому циклі завжди знайдеться, інакше був би гамільтоновим.
Тоді і не належить множині вершин , інакше вершина була б не потрібна. Більш того, вершина не суміжна з , інакше була б не потрібна. Далі, якщо в циклі є вершина суміжна з вершиною , то не суміжна з вершиною , оскільки в противному разі можна було б побудувати гамільтонів цикл без вершини .
Звідси слідує, що число вершин графа , не суміжних з , не менше числа вершин суміжних з .
Для будь-якої вершини графа попобудові, для вершини - аналогічно . Загальна кількість вершин суміжних і несуміжних з .
Таким чином маємо:
Прийшли до протиріччя.
Рис. 22.1 - Приклади гамільтонових і ейлерових графів.
Питання для самоперевірки та вправи
1. Який граф називається ейлеровим ?
2. Які основні властивості ейлерових графів ? Доведіть.
3. Який граф називається гамільтоновим ?
4. Які ознаки гамільтонових графів вам відомі ?
5. Чи являються ейлеровими, гамільтоновими чи тими і іншими графи, зображені на рис. 22.1 ?
6. Показати, що в є різних гамільтонових циклів.
7. Довести, що найбільша кількість ребер уграфів, які мають вершин і не мають трикутників дорівнює .
Лекція №23. Дерева
Означення дерева, ліса
Центри і центроїди
Теореми про граф – дерево
Граф називається ациклічним, якщо в ньому немає циклів.
Дерево – це зв’язний ациклічний граф.
Кожний граф, який не має циклів називається лісом. Компонентами лісу являються дерева.
Рис. 23.1 – приклади дерев та лісу.
Теорема 23.1 Для графа наступні ствердження еквівалентні:
(1) - дерево;
(2) будь-які дві вершини в з’єднані єдиним простим ланцюгом;
(3) - зв’язний граф і ;
(4) - ациклічний граф ;
(5) - ациклічний граф і якщо будь-яку пару несуміжних вершин з’єднати ребром , то в графі буде точно один простий цикл.
Доведення:
: Оскільки - зв’язний, то будь-які дві його вершини з’єднані простим ланцюгом. Нехай і - два різних простих ланцюга, що з’єднують вершини і , і нехай - перша вершина, що належить , така, що , . Але вершина, яка їй передує не належить і ми одержуємо два простих цикли, .
Якщо ж спільними для і є тільки вершини і , то все рівно одержимо цикл - одержали протиріччя, оскільки дерево – це ациклічний граф.
: Співвідношення доведемо по індукції. Ствердження очевидне для графів з одною і двома вершинами.
Припустимо, що воно вірне для графів, які мають менше вершин. Якщо ж граф має вершин, то вилучення з нього будь-якого ребра робить його незв’язним в силу того, що будь-які дві вершини графа з’єднані єдиним простим ланцюгом.
Більш того, граф, який ми одержуємо, має в точності дві компоненти зв’язності і в кожній з них менше, ніж вершин.
В кожній компоненті вершин на одну більше, ніж ребер, по індукційному припущенню.
Тоді для графа справедливо:
, але , а , отже,
: Припустимо, що в графі є простий цикл довжини . Цей цикл має вершин і ребер. А для будь-якої з вершин, які не належать циклу, існує інцидентне їй ребро, яке належить геодезичній, яка йде від деякої вершини циклу.
Усі такі ребра попарно різні. З цього слідує, що . Прийшли до протиріччя. Отже, в графі немає циклу.
: - ациклічний граф. З цього слідує, що будь-які дві його вершини з’єднані єдиним простим ланцюгом.
Нехай будь-які вершини і мають геодезичну більшу, ніж 1. Тоді, якщо долучити ребро , то ребро разом з простим ланцюгом, що з’єднує , створює простий цикл, який також єдиний.
Означення 23.1 Вершина називається кінцевою (або висячою), якщо її ступінь дорівнює 1, тобто існує єдине ребро, яке інцидентне . Таке ребро називається кінцевим.
Оскільки для будь-якого графа справедлива формула:
,
то для дерева формула приймає вигляд:
Очевидне ствердження: будь-яке нетривіальне скінчене дерево має хоча б дві кінцеві вершини і одне кінцеве ребро.
Доведення:
Оскільки дерево – це зв’язний нетривіальний граф, то не існує вершини, ступінь якої дорівнює 0. А отже, мінімальна ступінь .
Але в скінченому графі кількість вершин непарного ступеню парна.
Центри і центроїди
Ексцентриситет вершини в зв’язному графі визначається як по всім вершинам в графі .
Радіусом називається найменший з ексцентриситетів вершин.
Відмітимо, що найбільший з ексцентриситетів дорівнює діаметру графа.
Вершина називається центральною вершиною графа , якщо .
Центр графа - це множина усіх центральних вершин.
Рис. 23.2 – граф з центральними вершинами і .
Біля кожної вершини позначений її ексцентриситет.
Центр складається з двох вершин і .
Теорема 23.2 Кожне дерево має центр, який складається або з однієї вершини, або з двох суміжних.
Доведення:
Ствердження очевидне для дерев і :
Покажемо, що у будь-якого дерева ті самі центральні вершини, що і у дерева , одержаного з вилученням усіх його висячих вершин.
Ясно, що відстань від даної вершини дерева до будь-якої іншої вершини може досягати найбільшого значення тільки тоді, коли - висяча вершина.
Таким чином, ексцентриситет кожної вершини дерева точно на одиницю менше ексцентриситету цієї ж вершини дерева . Звідки слідує, що вершини дерева , які мають найменший ексцентриситет в співпадають з вершинами, що мають найменший ексцентриситет в . Таким чином, центри в і співпадають.
Якщо продовжити процес вилучення висячих вершин, то ми одержимо послідовність дерев з тим самим центром, що і у дерева .
В силу скінченності графа ми обов’язково прийдемо або до , або до .
Таким чином, в будь-якому випадку всі вершини дерева, одержані таким способом, утворюють центр дерева , який складається або з єдиної вершини, або з двох суміжних.
Гілка до вершини дерева - це максимальне піддерево, яке містить , як висячу вершину. Таким чином, число гілок до дорівнює .
Вага вершини дерева визначається кількістю ребер у найбільшій гілці до вершини .
Рис. 23.3 – приклад графа з зваженими вершинами.
Біля вершин позначена вага для кожної не висячої вершини. Ясно, що вага кожної висячої вершини дорівнює кількості ребер в дереві, а саме 14.
Вершина називається центроїдною вершиною дерева , якщо має найменшу вагу.
Центроїд дерева складається з усіх таких вершин.
Теорема 23.3 Кожне дерево має центроїд, який складається або з однієї вершини, або з двох суміжних вершин.