КМиИсО

1Остовные деревья минимального веса. Алгоритмы Прима и Краскала.

1.1Основные определения

Пусть V -некоторое конечное множество, V (2)-множество всех его двухэле- ментных подмножеств f 1; 2g таких, что 1 6= 2.

Определение 1.1 Неориентированным графом называют пару

G = (V; E), ãäå E V (2);при этом элементы множества V называют вершинами графа G,а элементы u; множества E - ребрами графа G.

Определение 1.2 Степенью вершины (deg ) называется число выходящих из нее ребер. Если степень вершины равна 0 (deg = 0), то называется изолированной. Если deg = 1, - висячей.

Определение 1.3 Маршрутом называется последовательность

i1 ; i2 ; :::; ik (èëè e1; e2; :::el), ãäå is 2 V (ei 2 E).

Маршрут называется цепью, если в нем нет повторяющихся ребер. Цепь называется простой, если в ней нет повторяющихся вершин (кро-

ме, быть может, начала и конца).

Циклический маршрут - это маршрут, у которого совпадают начало и конец. Цикл - циклическая цепь, а простой цикл - простая циклическая цепь.

Определение 1.4 Граф называют связным, если любые его две вершины можно соединить маршрутом.

Определение 1.5 Подграфом графа G = (V; E) называется такой граф G0; множество вершин которого V 0 является подмножеством множества V (V 0 V ), а множество ребер E0 - множества E(E0 E).

Определение 1.6 Лес - это граф без циклов.

Дерево - это связный граф без циклов (или связный лес).

Определение 1.7 Остов (или остовное дерево)графа G - это такой под-

граф G графа G ,который является деревом и содержит все вершины графа

G.

1

1.2Постановка задачи

Постановка задачи. Пусть имеется связный граф, каждому ребру которого поставлено в соответствие неотрицательное число, называемое весом ребра. Требуется найти остовное дерево минимального веса (вес дерева равен сумме весов ребер, входящих в него).

Простейшей интерпритацией задачи является построение сети дорог, имеющей минимальную длину, так, что они соединяют все заданные n городов.

Ниже предлагается два близких по идее алгоритма нахождения остовных деревьев минимального веса.

1.3Алгоритм Прима

Шаг 1. На первом шаге в качестве подграфа G1 G выбирается граф, который имеет одно ребро, выбранное из ребер графа G, имеющих минимальный вес.

На каждом последующем шаге к уже построенному графу добавляется одно ребро.

Øàã ê. Åñëè Gk 1 G уже построен, то граф Gk G получается из Gk 1 добавлением ребра l, обладающего следующими свойствами:

1)Один конец l принадлежит Gk 1, а другой - нет.

2)l имеет минимальный вес среди ребер,удовлетворяющих условию 1).

Теорема 1.1 Пусть G = (V; E) и jV j = n. Тогда граф Gn 1, построенный по алгоритму Прима, является остовным деревом минимального веса

äëÿ G.

Теорема 1.2 С помощью алгоритма Прима можно построить любое остовное дерево минимального веса.

1.4Алгоритм Краскала

Шаг 1. На первом шаге в качестве подграфа G1 G выбирается граф, который имеет одно ребро, выбранное из ребер графа G, имеющих минимальный вес.

2

Øàã ê. Åñëè Gk 1 G уже построен, то Gk G получается из Gk 1 добавле-

нием ребра l, обладающего следующими свойствами:

1)при добавлении l ê Gk 1 не образуется циклов,

2)l имеет минимальный вес среди ребер, удовлетворяющих условию 1).

Теорема 1.3 Пусть G = (V; E) и jV j = n.Тогда Gn 1- остовное дерево минимального веса для G.

Теорема 1.4 С помощью алгоритма Краскала можно построить любое остовное дерево минимального веса.

1.5Пример

Дан граф с заданными весами ребер.Найти остовное дерево минимального веса.

Приведем два решения с помощью алгоритмов Прима и Краскала.

1)С помощью алгоритма Прима получаем следующее остовное дерево минимального веса:

3

где последовательность выбираемых ребер-

fa; bgfb; egfd; egfe; hgfg; hgfe; cgfe; igfi; fg

вес дерева:1 + 2 + 1 + 2 + 1 + 3 + 2 + 1 = 13:

Замечание. C помощью этого же алгоритма можно получить и другие остовные деревья, например

fg; hgfg; egfe; dgfd; bgfb; agfe; cgfe; fgff; ig

2)С помощью алгоритма Краскала можно получить следующее остовное дерево минимального веса:

где последовательность выбираемых ребер-

fa; bgfd; egfg; hgfi; fgfe; hgfd; bgfe; cgfh; ig

вес дерева:1 + 1 + 1 + 1 + 2 + 2 + 2 + 3 = 13:

4

Замечание. Как видно из примера, с помощью алгоритмов Прима и Краскала можно получить различные остовные деревья , но в силу корректности алгоритмов вес построенных деревьев обязательно будет минимальным.

5

2 Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дийкстры

2.1Основные определения

Пусть теперь V конечное множество, V 2 - множество упорядоченных пар

( i; j)

Определение 2.1 Ориентированным графом называется пара (V; E),где E V 2. Элементы множества V называются вершинами графа

G = (V; E), а элементы множества E- его дугами.

Определение 2.2 Ориентированный маршрут это последовательность 1e1 2e2::: k 1ek 1 k, где каждая дуга ei = ( i; i+1) 2 E .

Определение 2.3 Ориентированная цепьэто ориентированный маршрут, состоящий из разных дуг.

Определение 2.4 Путьэто ориентированная цепь, у которой все вершины разные, кроме, быть может, начала и конца.

Определение 2.5 Ориентированный цикл - ориентированная цепь, у которой начало совпадает с концом.

Определение 2.6 Контур - это путь, у которого начало совпадает с концом.

2.2Постановка задачи

Постановка задачи. Пусть дан ориентированный граф G = (V; E) с заданными неотрицательными длинами ребер l(e) > 0; e 2 E. Нужно найти кратчайший путь, соединяющий две фиксированные вершины s è t, ãäå s- начало, а t-конец пути.

Для решения данной задачи может быть использован алгоритм Дийкстры. Идея алгоритма. Идея алгоритма состоит в упорядочивании вершин

по их расстоянию от s. Алгоритм работает следующим образом. Сначала

6

находим ближайшую к s вершину, ставим ей в соответствие число, равное расстоянию от s до этой вершины. На каждом очередном шаге алгоритма определяем следующую "по близости" к s вершину, фиксируем полученное расстояние и называем его постоянной меткой. Алгоритм продолжает работать до тех пор, пока постоянную метку не получит вершина t.

2.3Алгоритм Дийкстры

На всем протяжении работы алгоритма каждая вершина имеет либо временную метку l0(u), либо постоянную метку l(u).

Шаг 1. Положим: l(s) = 0;

l0(u) = +1 для всех остальных вершин u графа.

Шаг 2. Выберем вершину u с постоянной меткой. Рассмотрим все вершины , имеющие временную метку и для которых в графе существуют дуги (u; ). Для каждой такой вершины вычислим

l0( ) = minfl(u) + l(u; ); l0( )g

.

Шаг 3. Среди всех вершин с временными метками выбираем вершину r с минимальной временной меткой l0(r) и присваиваем ей постоянную метку.

Åñëè r = t, то задача решена, если нет - возвращаемся к шагу 2.

Теорема 2.1 Алгоритм Дийкстры последовательно выстраивает вершины S = S1; :::; Sn = t в порядке возрастания расстояний от них до S, причем l(Sk) - минимальное расстояние от S до Sk.

Замечание. С помощью алгоритма Дийкстры можно найти кратчайшие пути от вершины s до всех остальных вершин графа. Для этого работу ал-

горитма продолжают до тех пор, пока все вершины не получат постоянные метки.

7

2.4Пример

Задан граф с фиксированными длинами ребер:

Решение.

1.l(s) = 0; l0( ) = 1; 6= s.

2.Производим перерасчет чисел l0(u) для вершин u, не имеющих постоян-

ных меток и смежных с s.

l0(a) = minfl0(a); l(s) + l(s; a)g = minf1; 0 + 4g = 4;

l0(b) = minfl0(b); l(s) + l(s; b)g = minf1; 0 + 7g = 7;

l0(c) = minfl0(c); l(s) + l(s; c)g = minf1; 0 + 3g = 3:

Таким образом, первой ближайшей к s является вершина c, которой мы присваиваем постоянную метку l(s) и окрашиваем дугу (s; c).

3. l(c) = 3.

8

Так как вершина t не имеет постоянной метки, опять повторяем Шаг 2

алгоритма.

Производим снова перерасчет меток у вершин, смежных с последней вершиной, получившей постоянную метку (вершиной c). В данном случаеэто

единственная вершина d.

l0(d) = minfl0(d); l(c) + l(c; d)g = minf1; 3 + 3g = 6:

Метки остальных вершин оставляем без изменения.

l0(a) = 4;

l0(b) = 7; l0(t) = 1:

Минимум достигается в вершине a. Присваиваем ей метку и окрашиваем дугу (s; a) (на которой получен минимум). Вершина a становится вершиной, получившей постоянную метку.

4. l(a) = 4

9

Вершина t по-прежнему не имеет постоянной метки, поэтому снова повто-

ðÿåì Øàã 2.

Пересчитываем l0(u) у вершин, соседних с a; - вершин b è d.

l0(b) = minfl0(b); l(a) + l(a; b)g = minf7; 4 + 3g = 7:

l0(d) = minfl0(d); l(a) + l(a; d)g = minf6; 4 + 2g = 6: l0(t) = 1

10