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

Построить минимальное остовное дерево для неориентированного графа $\mathfrak {G}=(V, E)$ с множествами вершин $V=\left\{ v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}, v_{8}, v_{9}\right\}$ и рёбер $E=\left\{ \left(v_{1}, v_{2} ; 18\right),\left(v_{1}, v_{3} ; 2\right),\left(v_{3}, v_{2} ; 4\right),\left(v_{3}, v_{4} ; 6\right),\left(v_{3}, v_{5} ; 8\right),\left(v_{4}, v_{6} ; 5\right),\left(v_{5}, v_{4} ; 4\right),\left(v_{6}, v_{1} ; 7\right),\left(v_{6}, v_{8} ; 4\right),\left(v_{6}, v_{7} ; 3\right),\left(v_{7}, v_{5} ; 1\right),\left(v_{7}, v_{8} ; 7\right),\left(v_{8}, v_{1} ; 5\right),\left(v_{8}, v_{9} ; 3\right),\left(v_{9}, v_{1} ; 1\right)\right\}$. Третий параметр в скобках — вес ребра.

Пусть $e$ — ребро максимального веса в некотором простом цикле $C$ графа $\mathfrak {G}=(V, E)$. Доказать, что

Пусть $\mathfrak {T}=(V, T)$ — минимальное остовное дерево для нагруженного неориентированного графа $\mathfrak {G}=(V, E)$ с $n$ вершинами, $c$ — разметка рёбер. Пусть $(e_{1}, e_{2}, \ldots , e_{n-1})$ — это последовательность рёбер из $T$, упорядоченных по возрастанию $c\left(e_{i}\right)$. Пусть $\mathfrak {T}^{\prime }$ — произвольное остовное дерево для $\mathfrak {G}$ с рёбрами $\left(d_{1}, d_{2}, \ldots , d_{n-1}\right)$, упорядоченными по возрастанию $c\left(d_{i}\right)$. Показать, что $c\left(e_{i}\right) \leqslant c\left(d_{i}\right)$ для всех $i=1, \ldots , n-1$. Указание. Рассмотреть лес деревьев $\mathfrak {T}_{i, m}$ из рёбер $e_{j}, j<i$, и рёбра $d_{\ell }, \ell \leqslant i$.

Недостатком алгоритма Крускала является необходимость проверки на каждом шаге наличия циклов, что само по себе является достаточно сложной задачей. Следующий алгоритм независимо предложен В. Ярником, Р. Примом и Э. Дейкстрой.

1. Выбрать произвольным образом вершину $a$, она сама по себе является деревом (без рёбер).

2. На каждом шаге добавлять к имеющемуся дереву ребро наименьшего веса, одна из вершин которого принадлежит дереву, а вторая — нет. Доказать корректность этого алгоритма для связных графов по аналогии с теоремой 80 (Корректность алгоритма Крускала): результатом работы алгоритма МинОД$(\mathfrak {G}, c)$ является минимальное остовное дерево входного графа $\mathfrak {G}=(V, E)$ с функцией разметки $c$.

Пусть $\mathfrak {T}=(V, T)$ — это глубинное остовное дерево, построенное алгоритмом обхода в глубину для графа $\mathfrak {G}=(V, E)$. Доказать, что для каждого обратного ребра $(u, v) \in E \backslash T$ или $u$ является предком $v$ в $\mathfrak {T}$, или $v$ является предком $u$ в $\mathfrak {T}$.

Модифицировать алгоритм поиска в глубину так, чтобы он вычислял $\operatorname {Up}[v]$ и распечатывал список всех мостов графа.

Начиная с вершины $v_{1}$, обойти (занумеровать) вершины заданного неориентированного графа $\mathfrak {G}=(V, E)$ с помощью алгоритма обхода «в глубину» и построить дерево этого обхода. $V=\left\{ v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}, v_{8}, v_{9}, v_{10}\right\} , E=\left\{ \left(v_{1}, v_{2}\right),\left(v_{1}, v_{4}\right),\left(v_{1}, v_{8}\right),\left(v_{7}, v_{8}\right),\left(v_{2}, v_{9}\right),\left(v_{9}, v_{5}\right),\left(v_{3}, v_{8}\right),\left(v_{6}, v_{3}\right),\left(v_{3}, v_{7}\right),\left(v_{6}, v_{7}\right),\left(v_{10}, v_{9}\right),\left(v_{10}, v_{5}\right)\right\}$. Какое обратное ребро $e \in E \backslash T$ и цикл в $\mathfrak {G}$ обнаружились в этом обходе первыми? Вычислить для каждой вершины $v$ значение $\operatorname {Up}[v]$ и определить все мосты графа $\mathfrak {G}$. Считать, что все списки смежности упорядочены по возрастанию номера вершины, а выбирается вершина с наименьшим номером.

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

Если в ориентированном графе $\mathfrak {G}=(V, E)$ существует вершина $r$, из которой достижимы все остальные, то для него тоже можно определить понятие остовного (теперь ориентированного) дерева: дерево $\mathfrak {T}=(V, T)$ с корнем $r$. Определить, какие из алгоритмов построения остовного дерева можно приспособить для построения остовного дерева в ориентированном графе: алгоритм Крускала, алгоритм Ярника-Прима-Дейкстры, алгоритм поиска в глубину.

Определить для следующего нагруженного графа $\mathfrak {G}=(V, E)$ и вершины $a \in V$ длины кратчайших путей из $a$ в остальные вершины $\mathfrak {G}$ и построить дерево этих путей. Здесь $V=\left\{ a, b, c, d, e, f\right\} , E=\left\{ (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)\right\}$.

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

Теорема 83 (Корректность алгоритма Дейкстры): алгоритм Дейкстры строит дерево кратчайших путей из вершины $a$ во все достижимые из неё вершины и для каждой такой вершины $v$ определяет длину $D[v]$ кратчайшего пути в неё из $a$. В доказательстве, индукцией по $k$: обозначим с помощью $R_{k}$, $D_{k}$, $F_{k}$ значение $R$ и содержимое массивов $D$, $F$ после $k$ шагов выполнения цикла, а $w_{k}$ — вершину, выбранную на $(k+1)$-м шаге.

Показать, что в доказательстве индукционного шага теоремы 83 на стр. 248 вершина $w_{k}$ может быть только предпоследней в кратчайшем пути из $a$ в $u \in V \backslash \left(R_{k} \cup \left\{ w_{k}\right\} \right)$.

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

Пусть в графе $\mathfrak {G}$ выбрана вершина $a$ и для каждой вершины $v \in V$, достижимой из $a$, существует единственный кратчайший путь из $a$ в $v$. Доказать, что рёбра всех этих путей образуют ориентированное дерево с корнем $a$.