Три алгоритма на графах

Построение минимального остова

Во многих задачах в заданном графе нужно выделить некоторую часть, обладающую тем или иным свойством.

Определение 11.1. Граф G1=(V1,E1) называется подграфом графа G=(V,E), если $$V_{1} \subseteq V$$ и $$E_{1} \subseteq E$$.

Для неориентированных связных графов одним из интересных классов подграфов являются деревья, сохраняющие связность вершин. Они называются остовами, остовными деревьями, каркасами или скелетами графа.

Определение 11.2. Остовом (неориентированного) связного графа G=(V,E) называется его подграф S=(V,T), являющийся деревом.

Пусть задана функция c: E -> R, приписывающая каждому ребру $$e \in E$$ его стоимость (вес, длину) $$c(e) \in R$$ ( R - множество вещественных чисел). Тогда стоимость c(S) дерева S определяется как сумма стоимостей всех его ребер, т.е. $$c(S) = \sum_{ e \in T} c(e)$$.

Минимальным остовом называется остов минимальной стоимости.

Таким образом, минимальный остов - это самая дешевая (короткая) система путей, связывающая все вершины G.

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

Алгоритм МинОстов

Вход: связный граф G=(V,E) и функция стоимости ребер c: E -> R.

Выход: минимальный остов S=(V,T).

Этап 1. Пусть E содержит m ребер. Упорядочим их по возрастанию стоимостей:

$$E= \{ e_1, e_2, \ldots, e_i, \ldots , e_m\} \text{ так, что } c(e_1) \leq c(e_2) \leq \ldots \leq c(e_i) \leq \ldots \leq c(e_m)$$

Этап 2. Последовательно для каждого i =1, ... , m определим множество ребер Ti:

$$\indent \indent\indent T_1 = \{e_1\};\\ \indent\indent\indent \ldots\\ T_{i} = \left\{ \begin{array}{ll} T_{i-1} \cup \{e_i\}, \mbox{ если во множестве } T_{i-1} \cup \{e_i\} \mbox{ нет циклов}\\ T_{i-1}, \mbox{ в противном случае} \\ \end{array}\right. \indent\indent\indent \\$$

Положим T=Tm.

Выдать в качестве результата граф S=(V,T).

Докажем, что этот алгоритм корректен.

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

Доказательство Пусть результатом работы МинОстов на графе G=(V,E) является граф S=(V,T). Отметим вначале, что S является деревом. Действительно, отсутствие циклов следует из определения множеств Ti. Предположим, что S не является связным. Тогда должны существовать две вершины $$u, v \in V$$, которые не достижимы друг из друга в S. Но граф G связен, поэтому в нем есть путь из u в v. Тогда на этом пути обязательно имеется такое ребро $$e_{i}=(a,b)\in (E \setminus T)$$, у которого один конец a соединен путем с u в графе S, а второй конец b - нет. Но тогда на шаге i ребро ei должно попасть в Ti, так как его добавление не образует цикла. Следовательно, граф S связен.

Покажем теперь, что дерево S имеет минимальную стоимость. Пусть T={d1, ...,dk, ..., dn-1} - упорядочение всех ребер T по стоимости.

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

Пусть S'=(V,T') - минимальный остов, у которого (k-1) наименьших по стоимости ребер совпадают с ребрами T, т.е. упорядочение всех его ребер имеет вид: T'={f1=d1, ..., fk-1= dk-1, fk, ..., fn-1} и $$f_{k} \ne d_{k}$$. Пусть dk=(u,v). В T' имеется некоторый путь p из u в v, который не содержит ребро dk. На этом пути обязательно есть некоторое ребро f=(u''), не попавшее в T, иначе в T образовался бы цикл. Из построения T следует, что c(dk) <= c(f). Рассмотрим граф $$S''=(V, T'' \setminus \{ f\} )\cup \{ d_{k}\}$$. Очевидно, что этот граф является остовным деревом. Действительно, связь между u' и v' сохранилась, так как в S'' имеется путь: $$u' \leftrightarrow \dots \leftrightarrow u$$ $$\stackrel{d_k}{\leftrightarrow}$$ $$v \leftrightarrow \dots \leftrightarrow v'$$. Поэтому 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.

(рис 11.1) Граф G

Применим к нему алгоритм МинОстов. На первом этапе упорядочим все ребра, а на втором - рядом с каждым из них определим соответствующее множество Ti. Ребра, попавшие в T, будем по ходу вычисления отмечать знаком '+', а не попавшие - знаком '-'.

$$\begin{array}{cccl} \textbf{ E} \textbf{ c(e)} \textbf{ входит } T_i\\ (a,g) 1 + T_1 = \{ (a,g)\} \\ (g,e) 3 + T_2= \{ (a,g), (g,e)\}\\ (g,c) 4 + T_3 =\{ (a,g), (g,e), (g,c)\}\\ (e,d) 4 + T_4 =\{ (a,g), (g,e), (g,c), (e,d)\}\\ (a,b) 5 + T_5 =\{ (a,g), (g,e), (g,c), (e,d), (a,b)\}\\ \end{array}$$ $$\begin{array}{cccl} \textbf{ E} \textbf{ c(e)} \textbf{ входит } T_i\\ (b,c) 6 - T_6=T_5\\ (d,g)) 7 - T_7=T_6\\ (f,g) 8 + T_8 =\{ (a,g), (g,e), (g,c), (e,d), (a,b), (f,g)\}\\ (e,f) 11 - T_9=T_8 \\ (c,d) 12 - T_{10}=T_9\\ (a,f) 15 - T_{11}=T_{10} \end{array}$$

Таким образом, мы построили для G минимальный остов S=(V,T), где T=T8 ={ (a,g), (g,e), (g,c), (e,d), (a,b), (f,g)}. Он показан на рис. 11.2. Стоимость этого остова c(S)=25.

(рис 11.2) Минимальный остов S=(V,T) для графа G

Замечание. Так как дерево с n вершинами содержит в точности (n-1) ребер, то работу алгоритма МинОстов можно прекращать после такого шага i, на котором в Ti окажется |V| - 1 ребер. В нашем примере |V| =7 и алгоритм мог остановиться после 8-го шага.

Поиск в глубину и задача о лабиринте

Задача поиска выхода из лабиринта известна с древних времен. В терминах графов ее можно формализовать так: лабиринт - это неориентированный граф, вершины которого представляют "перекрестки" лабиринта, а ребра - дорожки между соседними перекрестками. Одна или несколько вершин отмечены как выходы. Задача состоит в построении пути из некоторой исходной вершины в вершину-выход.

В этом разделе мы рассмотрим метод обхода всех вершин графа, называемый поиском в глубину. Его идею кратко можно описать так:

находясь в некоторой вершине v, идем из нее в произвольную еще не посещенную смежную вершину w, если такой вершины нет, то возвращаемся в вершину, из которой мы пришли в v.

Алгоритм поиска в глубину

Вход: G=(V, E) - неориентированный граф, представленный списками смежностей: для каждой $$v \in V$$ список Lv содержит перечень всех смежных с v вершин.

Выход: NUM[v] - массив с номерами вершин в порядке их прохождения и множество (древесных) ребер $$T \subseteq E$$, по которым осуществляется обход.

Алгоритм ПОГ

T = {}; NOMER = 1;

для каждой вершины $$v \in V$$ положим NUM[v] = 0 и пометим v как "новую";

ПОКА существует "новая" вершина $$v \in V$$

ВЫПОЛНЯТЬ ПОИСК(v).

Основную роль в этом алгоритме играет следующая рекурсивная процедура.

Алгоритм ПОИСК(v):

1.   пометить v как "старую";
2.   NUM[v] = NOMER;  NOMER = NOMER + 1;
3.   ДЛЯ КАЖДОЙ   w принадлежащей Lv   ВЫПОЛНЯТЬ
4.         ЕСЛИ   вершина   w   "новая"
5.            ТО
6.            { добавить (v, w)   к   T;
7.               ПОИСК(w);
8.            }

Теорема 11.2. Алгоритм ПОГ обходит (нумерует) все вершины графа G=(V,E). Если G - связный граф, то S=(V,T) - это остов G, если граф G не является связным, то S=(V,T) - это остовной лес для G, т.е. объединение остовных деревьев для каждой из компонент связности G.

Доказательство Первое утверждение следует из того, что по окончании алгоритма ПОГ все вершины графа старые, а это значит, что для каждой из них вызывалась процедура ПОИСК, которая в стр.2 присвоила номер.

Заметим теперь, что если ребро (v, w) попадает в T, то вызов процедуры ПОИСК(w) происходит после вызова ПОИСК(v) и поэтому NUM[v] < NUM[w]. Существование цикла в S означало бы, что для некоторого ребра из T это свойство нарушено (почему?). Следовательно, в S циклов нет.

Пусть G1=(V1,E1) - связная компонента G и $$v_{1} \in V_{1}$$ - первая ее вершина, для которой вызывается процедура ПОИСК. Тогда для каждой вершины $$w \in V_{1}$$ внутри вызова ПОИСК(v1) произойдет вызов ПОИСК(w).

Это утверждение доказывается индукцией по расстоянию ( длине кратчайшего пути ) от v1 до w.

Если это расстояние равно 1, то $$w \in L_{v1}$$ и рассматривается в вызове ПОИСК(v1) в стр.3. Если w в этот момент "старая", то, значит, ПОИСК(w) уже вызывался. Если же w "новая", то в стр. 7 происходит вызов ПОИСК(w).

Предположим теперь, что ПОИСК(u) вызывается для всех вершин u, находящихся на расстоянии k >= 1 от v1, и пусть вершина $$w \in L\_ \{ v_{1}\}$$ находится на рсстоянии (k + 1) от v1. Тогда имеется путь длины (k + 1) от v1 до w . Пусть u - это предпоследняя вершина на этом пути. Тогда расстояние от v1 до u равно k и по нашему предпроложению в некоторый момент выполняется вызов ПОИСК(u). Так как $$w \in L_{u}$$, то в этом вызове вершина w в некоторый момент рассматривается в цикле в стр.3. Как и выше, если она в этот момент "старая", то ПОИСК(w) уже вызывался. Если же w еще "новая", то в стр.7 происходит вызов ПОИСК(w).

Также по индукции замечаем, что если вызов ПОИСК(w) произошел внутри вызова ПОИСК(v), то в T имеется путь из v в w. Следовательно, граф S1=(V1,T1), построенный в процессе вызова ПОИСК(v) является деревом с корнем v.

Дерево S=(V,T), которое строится алгоритмом ПОГ, называется глубинным остовом или глубинным остовным деревом графа G. Ребра, попавшие в множество T, называются прямыми, а не попавшие в это множество ребра из множества (E \ T) - обратными. Каждое обратное ребро (v,w) соединяет вершину v с ее предком w в глубинном остове (см. задачу 11.8). Поэтому в исходном графе G оно определяет цикл: от w к v по ребрам дерева T, а затем обратно от v к w по ребру (v,w). Поэтому алгоритм ПОГ можно использовать для проверки наличия циклов в G. Ребро (v,w) не добавляется к T, т.е. является обратным, тогда и только тогда, когда в стр.4 вызова ПОИСК(v) обнаруживается, что вершина w "старая". Поэтому, добавив в процедуру ПОИСК(v) последнюю строку

9.       ИНАЧЕ   ПЕЧАТЬ(v,w),

мы получим процедуру, которая в дополнение построению к глубинного остова графа будет распечатывать список всех обратных ребер. Если этот список не пуст, то в графе имеются циклы, иначе - нет.

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

Определение 11.3. Ребро (v,w) неориентированного графа G=(V,E) называется мостом G, если при его удалении из E число связных компонент графа увеличивается, т.е. в графе G'=(V, E \ { (v,w)} связных компонент больше, чем в G.

Из этого определения, в частности, следует, что ребро является мостом тогда и только тогда, когда оно не входит ни в какой цикл ( почему?). Поиск в глубину позволяет находить все мосты графа. Во-первых, заметим, что любой мост (v,w) является ребром глубинного остова, так как другого пути, связывающего v и w нет. Во-вторых, если это ребро ориентировано от v к w, то в глубинном остове нет обратных ребер, соединяющих w и его потомки с предками w. Это условие является и достаточным, так как, если таких ребер нет, то удаление (v,w) нарушит связь между v и w и они окажутся в разных компонентах связности. Обозначим через ВЕРХ(w) минимум из NUM[w] и наименьшего из номеров вершин, к которым ведут обратные ребра от вершин поддерева Tw. Тогда, учитывая, что обратные ребра соединяют потомков с предками и что номера предков меньше номеров потомков, предложенный критерий можно переформулировать в следующем виде.

Теорема 11.3. Ребро (v,w) глубинного остова D=(V,E) неориентированного графа G=(V,E) является мостом G тогда и только тогда, когда ВЕРХ(w) > NUM[v] или, что эквивалентно, ВЕРХ(w) = NUM[w].

Вычисление значения ВЕРХ(w) можно организовать в процессе обхода в глубину, используя следующее соотношение:

$$ВЕРХ(w)= \min \{ \{NUM[w]\} \cup \{\textrm{ВЕРХ}(z)\ |\ (v,z) - \textit{ прямое ребро }\}\cup \\ \cup \{NUM[u] | (w,u) - \textit{ обратное ребро }\} \}$$

Для этого достаточно в строку 2 алгоритма ПОГ добавить начальное присвоение ВЕРХ(v) := NUM[v], в строке 7 приписать после ПОИСК(w) присвоение ВЕРХ(v) := min {ВЕРХ(v), ВЕРХ(w)}, учитывающее прямые ребра, и добавить строку

9.         ИНАЧЕ   ВЕРХ(v) := min{ВЕРХ(v),NUM(w)}

для учета обратных ребер.

Зная значения ВЕРХ(w), нетрудно выявить все мосты, используя критерий из теоремы 11.3.

Пример 11.2. Применим алгоритм ПОГ к графу G2, изображенному на рис. 11.3.

(рис 11.3) Граф G2

Его представление в виде списков смежности имеет следующий вид:

$$\begin{array}{ll} L_1:\ 6, 2 L_7: 6, 8\\ L_2:\ 1, 9, 10, 3 L_8: 6, 7\\ L_3:\ 2, 5, 4 L_9: 2, 10, 11\\ L_4:\ 3, 5 L_{10}: 2,9, 11 \\ L_5:\ 2, 3, 4 L_{11}: 9, 10\\ L_6:\ 1, 7, 8 \end{array}$$

Алгоритм ПОГ вызовет процедуру ПОИСК(1). Эта процедура рекурсивно вызовет ПОИСК(6) и т.д. Вот структура всех получающихся вызовов процедуры ПОИСК:

$$\begin{array}{ccccccc} ПОИСК(1) \Rightarrow ПОИСК(6) \Rightarrow ПОИСК(7) \Rightarrow ПОИСК(8)\\ \Downarrow \\ ПОИСК(2) \Rightarrow ПОИСК(9) \Rightarrow ПОИСК(10) \Rightarrow ПОИСК(11)\\ \Downarrow \\ ПОИСК(3) \Rightarrow ПОИСК(5) \Rightarrow ПОИСК(4) \\ \end{array}$$

Вначале идут "горизонтальные" вызовы, затем возвраты справа налево и вызовы "по вертикали". В результате вершины G2 получат следующие номера, отражающие порядок их прохождения:

$$\begin{array}{rccccccccccc} V : 1 2 3 4 5 6 7 8 9 10 11\\ NUM : 1 5 9 11 10 2 3 4 6 7 8 \end{array}$$

Ребра остова $$T$$, построенные в процессе обхода графа, показаны на рис. 11.4. Стрелки указывают направление обхода. В скобках рядом с номером вершины указан ее номер в массиве NUM, т.е. номер в порядке обхода алгоритмом ПОГ.

(рис 11.4) Остовное "глубинное" дерево S=(V,T) графа G2

В процессе построения этого дерева были определены следующие обратные ребра: (8,6), (10,2), (11,9), (5,2) и (4,3). Нетрудно проверить, что добавление любого из этих ребер к T приводит к образованию простого цикла.

Используя расширенный вариант ПОГ с вычислением функции ВЕРХ, мы получим следующий результат:

$$\begin{array}{rccccccccccc} V : 1 2 3 4 5 6 7 8 9 10 11\\ NUM : 1 5 9 11 10 2 3 4 6 7 8 \\ \textrm{ВЕРХ} : 1 5 5 9 5 2 2 2 5 5 6 \end{array}$$

Так как ВЕРХ(2) =NUM[2] = 5 и ВЕРХ(6) =NUM[6] = 2, то по теореме 11.3 мостами графа G2 являются ребра (1,2) и (1,6) и других мостов у него нет.

Алгоритм поиска в глубину часто используется как основа для различных алгоритмов обработки графов. Вместо строки 6, в котрой вершина v получает номер NUM(v), можно вставить вызов любой процедуры, обрабатывающей информацию, связанную с этой вершиной (например, для задачи о лабиринте это может быть проверка того, что v является выходом из лабиринта). И тогда полученный вариант алгоритма обеспечит обработку всех вершин графа.

Задача о кратчайших путях из одного источника

Пусть G=(V,E) - ориентированный граф, для каждого ребра $$e \in E$$ которого указана его (неотрицательная) длина: c(e) >= 0. Тогда длина пути p=v1,v2, ... , vk+1 определяется как сумма длин ребер, входящих в этот путь: $$c(p) = \sum_{i=1}^k c(v_i,v_{i+1})$$. Если в G имеется путь из вершины a в вершину b, то имеется и такой путь минимальной длины. Он называется кратчайшим путем из a в b. Конечно, в графе может оказаться несколько различных кратчайших путей из a в b.

Естественно спросить, как узнать длину кратчайшего пути из a в b и построить его? Лучшие известные на сегодняшний день алгоритмы, отвечающие на этот вопрос, решают, на самом деле, более общую задачу построения всех кратчайших путей из одного источника: по вершине a найти длины кратчайших путей из a во все достижимые из нее вершины и построить для каждой из таких вершин некоторый кратчайший путь из a. Если для каждой вершины $$v \in V$$, достижимой из a, зафиксировать один кратчайший путь из a в v, то получившийся граф будет представлять ориентированное дерево с корнем a (докажите это!). Это дерево называется деревом кратчайших путей из a.

Мы рассмотрим алгоритм построения дерева кратчайших путей и определения их длин, предложенный в 1959г. Е. Дейкстрой. Его идея следующая: перед каждым этапом известно множество отмеченных вершин S, для которых кратчайшие пути найдены ранее; тогда на очередном этапе к нему добавляется вершина w, с самым коротким путем из a, проходящим по множеству S ; после этого пересчитываются длины кратчайших путей из a в оставшиеся вершины из V \ S с учетом новой вершины w. Длина текущего кратчайшего пути из a в v, проходящего по множеству S, заносится в ячейку D[v] массива D. В конце работы в этом массиве отыскиваются длины соответствующих кратчайших путей. Для определения дерева кратчайших путей служит массив ОТЕЦ, его элемент ОТЕЦ[v] содержит ссылку на вершину, из которой кратчайший путь приходит в v .

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

Вход: G=(V,E) - ориентированный граф, c(u,v) >= 0 -длина ребра $$(u,v) \in E$$ (если $$(u,v) \notin E$$, то считаем, что $$c(u,v) = \infty )$$ и исходная вершина $$a \in V$$.

=== ИНИЦИАЛИЗАЦИЯ === 	
1.   S := {a}; ' отметить a
2.   D[a] := 0; ' расстояние от a до a
3.   ДЛЯ КАЖДОЙ   v принадлежащей V, v != a   ВЫПОЛНЯТЬ
4.      {D[v] := c(a,v);   ' расстояние от a до v через a
5.      ЕСЛИ c(a,v) < бесконечности ТО ОТЕЦ[v]:= a   ИНАЧЕ   ОТЕЦ[v]:= - };
             === ОСНОВНОЙ ЦИКЛ === 
6.   ПОКА   V \ S не пусто    ВЫПОЛНЯТЬ ' есть неотмеченные вершины
7.      { выбрать неотмеченную вершину w с минимальным D[w];
8.      S := S  объединение с {w}; ' отметить w
9.      ДЛЯ КАЖДОЙ (неотмеченной) u принадлежит V \ S   ВЫПОЛНЯТЬ
10.         ЕСЛИ   D[u] > D[w] + c(w,u)
11.            ТО   { D[u] :=  D[w] + c(w,u);
12.                  ОТЕЦ[u]:= w}
13.      }

Пример 11.3. Рассмотрим работу этого алгоритма на нагруженном графе G=(V={a, b, c, d, e, f}, E) и выделенной вершине $$a \in V$$. Зададим длины ребер матрицей C= (cuv), где элемент cuv=c(u,v):

$$\[\left( \begin{array}{crrrrrr} a b c d e f \\ a 0 25 5 30 \infty 75\\ b 12 0 \infty \infty 120 20\\ c \infty 15 0 20 45 60\\ d \infty \infty \infty 0 23 20\\ e \infty \infty 75 20 0 20\\ f 40 15 15 26 \infty 0 \end{array} \right) \]$$

Поэтапную работу алгоритма Дейкстры удобно представлять в виде таблицы, строки которой соответствуют его этапам. Первый столбец - номер этапа, второй показывает изменение множества отмеченных вершин S, третий - вершину w, добавляемую к S на текущем шаге, четвертый - длину кратчайшего пути из a в w, затем идут столбцы со значениями элементов массивов D и ОТЕЦ.

Алгоритм Дейкстры на графе G.

N	S	w	D[w]	D					ОТЕЦ
				b	c	d	e	f	b	c	d	e	f
1.	a	c	5	25	5	30	$$\infty$$	75	a	a	a	-	a
2.	a, c	b	20	20	-	25	50	65	c	a	c	c	c
3.	a, c, b	d	25	-	-	25	50	40	c	a	c	c	b
4.	a, c, b,d	f	45	-	-	-	48	45	c	a	c	d	b
5.	a, c, b,d	e	45	-	-	-	-	45	c	a	c	d	b

Дерево кратчайших путей из вершины a задается массивом ОТЕЦ. Оно представлено на рис. 11.5.

(рис 11.5) Дерево кратчайших путей из вершины a в графе G

Теорема 11.4. (о корректности алгоритма Дейкстры)

Алгоритм Дейкстры строит дерево кратчайших путей из вершины a во все достижимые из нее вершины и для каждой такой вершины v определяет длину D[v] кратчайшего пути в нее из a.

Доказательство Докажем по индукции, что после каждого этапа алгоритма выполнены следующие условия:

для любой вершины $$v \in S$$ величина D[v] равна длине кратчайшего пути из a в v ;

для любой вершины $$v \in V \setminus S$$ величина D[v] равна длине кратчайшего пути из a в v, проходящего по множеству S ;

для каждой вершины v дерева T, задаваемого массивом ОТЕЦ, длина пути из корня a в v равна D[v].

Эти три условия очевидно выполняются после инициализации в строках 1- 5.

Предположим теперь, что они выполнены перед началом k -го этапа. Пусть w - вершина, добавляемая к S на k -ом этапе. По предположению, D[w] - длина кратчайшего пути из a в w, все вершины которого, кроме w, входят в S. Предположим, что есть другой более короткий путь p из a в w. Зафиксируем на этом пути первую вершину u, не входящую в S. По выбору p $$u\ne w$$. Поэтому путь p разбивается на две непустые части: путь p1 из a в u и путь p2 из u в w. Но по выбору w мы имеем, что длина p1 >= D[u] >= D[w]. Так как длина p2 неотрицательна, то длина p >= D[w], т.е. этот путь не короче пути, представленного в дереве T. Таким образом, D[w] - это длина кратчайшего пути из a в w. Следовательно, условие (а) выполнено и после k -го этапа.

Рассмотрим теперь произвольную вершину $$u \in V \setminus (S \cup \{ w\} )$$. Кратчайший путь p из a в u, проходящий по множеству $$S \cup \{ w\}$$, либо не включает вершину w и в этом случае его длина равна D[u] и он имеется в текущем дереве T, либо он проходит через w и составлен из кратчайшего пути из a в w через S, продолженного ребром (w,u). В последнем случае длина пути равна D[w] + c(w,u). Но в 10-ой строке алгоритма эти величины сравниваются и, если путь через w короче, то его длина становится новым значениием D[u] (строка 11) и он фиксируется в дереве T (строка 12). Следовательно, условия (б) и (в) также выполнены после k -го этапа.

Так как после завершения алгоритма S = V, то в завершающем дереве T представлены кратчайшие пути из a во все достижимые из нее вершины, а массив D содержит длины этих путей. Значение $$D[u]= \infty$$ указывает на то, что вершина u не достижима из вершины a.

Замечание о сложности. На каждом этапе (исполнении тела основного цикла в стр. 6 - 13) одна вершина добавляется во множество S. Поэтому таких этапов не более |V|. Чтобы выбрать в массиве D вершину w с минимальным D[w] (стр. 7), требуется не более |V| шагов. Перевычисление D[u] для каждой из вершин $$u \in (V\setminus S)$$ требует константного числа операций, поэтому весь цикл в стр. 9 - 12 потребует не более c |V| шагов. Отсюда получаем, что для некоторой константы c время выполнения алгоритма Дейкстры не превышает c |V|2. Поскольку размер любого представления исходного графа не меньше |V|, то алгоритм работает в квадратичное время (от размера входа).

Задачи

Задача 11.1. Цикл в связном неориентированном графе называется Эйлеровым, если он проходит по одному разу через каждое ребро графа. Докажите, что в таком графе имеется Эйлеров цикл тогда и только тогда, когда степени всех его вершин четны (такие графы называются четными.

Указание. Достаточность можно установить, доказав правильность следующей процедуры построения Эйлерова цикла.

Выбрать произвольную вершину a и построить цикл, начинающийся и закачивающийся в a, следуя правилу (*): прийдя в некоторую вершину, выйти из нее по произвольному ребру, еще не включенному в цикл.

Если построенный цикл содержит не все ребра, то выбрать среди вершин, через которые он проходит, произвольную вершину b, инцидентную еще не пройденному ребру (почему такая вершина найдется?), и построить, начиная с нее, цикл, следуя тому же правилу (*). Объединить этот цикл с построенным ранее.

Повторять пункт (2) до тех пор, пока построенный цикл не станет Эйлеровым.

Задача 11.2. Используя результаты предыдущей задачи, определить по неориентированному графу G=(V,E) четный ли он. Если он не является четным, то удалить из него минимальное число ребер, чтобы он стал четным. Построить в исходном или в получившемся после удаления ребер четном графе Эйлеров цикл.

V={a,b,c,e,f,g,h, k,m,n }, E={ (a,c), (a,h), (a,m),(a,k), (b,c),(b,k), (b,f), (b,m), (c,k), (c,m), (e,f), (e,g), (f,k), (f,n),(g,m), (g,h), (h,k), (h,m),(k,n) }.

Задача 11.3. Неориентированный граф G=(V,E) называется двудольным, если его вершины можно разбить на две непересекающихся части X и Y ( $$V=X \cup Y, X \setminus cap Y = \varnothing$$ ) так, что каждое ребро из $$e \in E$$ соединяет вершину из X с вершиной из Y. Такой граф также называется бихроматическим, так как его вершины можно раскрасить в два цвета так, что соседние вершины будут окрашены в разные цвета.

Докажите, что граф является двудольным тогда и только тогда, когда в нем нет циклов нечетной длины.

Указание. Достаточность можно установить, доказав правильность следующей процедуры разбиения V на X и Y:

Поместить произвольную вершину $$v \in V$$ в X и отметить ее знаком +.

ПОКА имеются неотмеченные вершины с отмеченными соседями

ВЫПОЛНЯТЬ {

Поместить все неотмеченные вершины с соседями из X в Y и отметить их знаком - ;

Поместить все неотмеченные вершины с соседями из Y в X и отметить их знаком +

};

ЕСЛИ после завершения цикла 2 в V остались неотмеченные вершины

ТО поместить произвольную такую вершину v в X, отметить ее знаком + и снова повторить цикл 2

ИНАЧЕ выдать в качестве результата полученные множества: X - вершины, отмеченные +, и Y - вершины, отмеченные -.

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

Задача 11.4. Используя результаты предыдущей задачи, определить, является ли заданный ниже неориентированный граф G=(V,E) двудольным. Если он не двудольный, то каково минимальное число ребер, которые нужно из него удалить, чтобы он стал двудольным? Приведите обоснование ответа.

V={a,b,c,e,f,g,h, k,m,n }, E={ (a,h), (a,n),(a,k), (b,k), (b,f), (b,m), (c,k), (c,h), (e,f), (e,g), (f,a), (f,m),(g,m), (m,n) }.

Задача 11.5. Найти минимальное остовное дерево для неориентированного графа G=(V,E), где V={v1,v2,v3,v4,v5,v6,v7,v8,v9}, E = {(v1,v2,18), (v1,v3,2), (v3,v2,4), (v3,v4,6), (v3,v5,8), (v4,v6,5), (v5,v4,4), (v6,v1,7), (v6,v8,4), (v6,v7,3), (v7,v5,1), (v7,v8,7), (v8,v1,5), (v8,v9,3), (v9,v1,1)} (третий параметр в скобках - стоимость ребра).

Задача 11.6. Пусть S= (V,T) - остовное дерево наименьшей стоимости, построенное алгоритмом МИНОД для нагруженного неориентированного графа G=(V,E) с n вершинами. Пусть c1 <= c2 <= ... <= cn-1 - это последовательность длин ребер из T, упорядоченных по возрастанию. Пусть S' - произвольное остовное дерево для G с длинами ребер d1 <= d2 <= ... <= dn-1. Показать, что ci <= di для всех i: 1 <= i <= n-1.

Задача 11.7. Пусть e - ребро максимального веса в некотором цикле графа G=(V,E). Докажите, что существует минимальный остов графа G'=(V,E \ {e}), который является также минимальным остовом графа G.

Задача 11.8. Пусть D=(V,T) - это глубинный остов, построенный алгоритмом обхода "в глубину" для графа G=(V, E). Докажите, что для каждого обратного ребра $$(u,v) \in E \setminus T$$ либо u является предком v в D, либо v является предком u в D.

Задача 11.9. Модифицируйте алгоритм поиска в глубину так, чтобы он вычислял функцию ВЕРХ(v) и распечатывал список всех мостов графа.

Задача 11.10. Обойти (занумеровать) вершины заданного неориентированного графа G с помощью алгоритма обхода "в глубину" и построить дерево этого обхода.

G = (V,E), где V = {v1,v2,v3,v4,v6,v7, v8,v9,v10,v11},

E ={(v1,v2),(v1,v4),(v1,v8),(v7,v8), (v2,v9),(v9,v11), (v3,v8),(v6,v3), (v3,v7),(v6,v7), (v10,v9), (v10,v11) }.

Какое обратное ребро $$e \in E \setminus T$$ и цикл в G обнаружились в этом обходе первыми? Вычислите для каждой вершины v значение ВЕРХ(v) и определите все мосты графа G.

Задача 11.11. Измените алгоритм обхода "в глубину" так, чтобы он позволил перечислить все связные компоненты неориентированного графа.

Задача 11.12. Определить для заданного нагруженного графа G=(V, E) и выделенной вершины $$a \in V$$ длины кратчайших путей из этой вершины в остальные вершины G и построить дерево этих путей.

V={a, b, c, d, e,f }, E= {(a,b; 154), (a,c; 17),(a,d; 214), (a,e; 63), (b, d; 25), (c,e; 33), (c, d; 192), ( c,b; 123), (d, f; 5), (e,f; 140), (d,e; 10)}, (здесь каждая скобка (u,v; D) задает ребро $$(u,v) \in E$$ и его "вес" c(u,v)=D ).

Задача 11.13. Где в доказательстве правильности алгоритма Дейкстры используется неотрицательность весов ребер? Приведите пример графа (с отрицательными весами), для которого алгоритм Дейкстры дает неверный ответ.

Задача 11.14. Докажите, что на каждом шаге алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S проходит только через вершины множества S.

Задача 11.15. Сколько раз может меняться для одной вершины v значение D[v] в ходе работы алгоритма Дейкстры для графа с 6 вершинами? Привести пример на каждый возможный случай.