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