Ноу Інти, лекція, три алгоритму на графах

Анотація: Побудова мінімального кістяка графа: алгоритм Круськала. Завдання про лабіринті і пошук в глибину на неорієнтованому графі. Знаходження найкоротших шляхів з одного джерела: алгоритм Дейкстри

Побудова мінімального кістяка

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

Визначення 11.1. Граф G1 = (V1, E1) називається подграфом графа G = (V, E). якщо і .

Для неорієнтованих зв'язкових графів одним з цікавих класів подграфов є дерева, що зберігають зв'язність вершин. Вони називаються остовами. кістяк. каркасами або скелетами графа.

Визначення 11.2. Кістяком (неорієнтованого) зв'язного графа G = (V, E) називається його підграф S = (V, T). є деревом.

Нехай задана функція c: E -> R. приписує кожному ребру його вартість (вага. Довжину) (R - безліч дійсних чисел). Тоді вартість c (S) дерева S визначається як сума вартостей всіх його ребер, тобто .

Мінімальним остовом називається остов мінімальної вартості.

Таким чином, мінімальний остов - це найдешевша (коротка) система шляхів, що зв'язує всі вершини G.

Опишемо процедуру побудови мінімального кістяка. запропоновану Дж. Крускалом в 1956р.

Доведемо, що цей алгоритм коректний.

Теорема 11.1. Алгоритм МінОстов будує мінімальний остов вхідного графа G = (V, E).

Доказ Нехай результатом роботи МінОстов на графі G = (V, E) є граф S = (V, T). Відзначимо спочатку, що S є деревом. Дійсно, відсутність циклів випливає з визначення множин Ti. Припустимо, що S не є зв'язковим. Тоді повинні існувати дві вершини, які недосяжні одна з одної в S. Але граф G зв'язний, тому в ньому є шлях з u в v. Тоді на цьому шляху обов'язково є таке ребро, у якого один кінець a з'єднаний шляхом з u в графі S. а другий кінець b - немає. Але тоді на кроці i ребро ei має потрапити в Ti. так як його додавання не утворює циклу. Отже, граф S зв'язний.

Покажемо тепер, що дерево S має мінімальну вартість. Нехай T = 1. dk. dn-1> - впорядкування всіх ребер T за вартістю.

Покажемо індукцією по k = 1. (N-1). що існує мінімальний остов. що включає ребра d1. dk.

Нехай S '= (V, T') - мінімальний остов. у якого (k-1) найменших за вартістю ребер збігаються з ребрами T. тобто впорядкування всіх його ребер має вигляд: T '= 1 = d1. fk-1 = dk-1. fk. fn-1> і. Нехай dk = (u, v). В T 'є певний шлях p з u в v. який не містить ребро dk. На цьому шляху обов'язково є якийсь ребро f = (u ''). що не потрапило в T. інакше в T утворився б цикл. З побудови T випливає, що c (dk) <= c(f). Рассмотрим граф . Очевидно, что этот граф является остовным деревом. Действительно, связь между u' и v' сохранилась, так как в S'' имеется путь. . Поэтому S'' - связный граф. Если бы в S'' был цикл, то он обязательно включал бы ребро dk. Но тогда часть этого цикла без ребра dk образовывала бы путь p' между u в v. не совпадающий с путем p. Следовательно, в дереве T' было бы два разных пути между u в v. что невозможно, так как тогда в T' был бы цикл. Отсюда заключаем, что в S'' циклов нет и S'' - остовное дерево. Его стоимость c(S'')= c(S') - c(f) + c(dk ) <= c(S'). Так как S' - минимальный остов. то c(S'')=c(S') и S'' - тоже минимальный остов. у которого с S имеется k общих ребер: d1. dk .

Тоді при k = n-1 отримуємо, що S - мінімальний остов.

Приклад 11.1. Розглянемо навантажений граф G. показаний на рис. 11.1.