Алгоритмы на графах

Построить минимальное остовное дерево для неориентированного графа $\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\}$. Третий параметр в скобках — вес ребра.

Найти минимальное остовное дерево для неориентированного графа $\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} ; 10\right),\left(v_{1}, v_{4} ; 6\right),\left(v_{2}, v_{3} ; 12\right),\left(v_{2}, v_{4} ; 3\right), \left(v_{3}, v_{5} ; 20\right),\left(v_{3}, v_{6} ; 11\right),\left(v_{4}, v_{5} ; 3\right),\left(v_{4}, v_{7} ; 2\right),\left(v_{5}, v_{6} ; 4\right),\left(v_{5}, v_{7} ; 2\right), \left(v_{5}, v_{8} ; 5\right),\left(v_{5}, v_{9} ; 9\right),\left(v_{6}, v_{8} ; 6\right),\left(v_{6}, v_{9} ; 17\right),\left(v_{8}, v_{9} ; 7\right)\right\}$.

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

Пусть $\mathfrak {T}=(V, T)$ — минимальное остовное дерево для нагруженного неориентированного графа $\mathfrak {G}=(V, E)$ с $n$ вершинами, $c-$ разметка рёбер. Пусть $\left(e_{1}, e_{2}, \ldots , e_{n-1}\right)$ — это последовательность рёбер из $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$.

Пусть все рёбра дерева имеют попарно различные веса. При каком условии в алгоритме МинОД минимальное остовное дерево будет построено на самом последнем шаге?

Доказать корректность следующего алгоритма построения минимального остовного дерева. Пока в графе есть циклы, выбирать некоторый простой цикл и выкидывать одно из рёбер наибольшего веса, среди входящих в этот цикл.

Пусть задан неориентированный нагруженный граф $\mathfrak {G}=(V, E)$, в котором $V=\left\{ a, b, c, d, e, f, g, h, k\right\}$ и $E=\left\{ (a, b ; 10),(a, c ; 7), (b, f ; 21),(b, d ; 9),(c, d ; 8),(d, e ; 21),(f, e ; 7),(f, g ; 8),(e, k ; 12), (e, h ; 10),(g, h ; 8)\right\}$. Какие из рёбер не могут попасть ни в какое минимальное остовное дерево?

Доказать корректность следующего алгоритма построения минимального остовного дерева, предложенного независимо В. Ярником, Р. Примом и Э. Дейкстрой.

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

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

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

Пусть задан неориентированный граф $\mathfrak {G}=(V, E)$ с множеством вершин $V=\left\{ a, b, c, d, e, f, g, h, i\right\}$ и множеством рёбер $E=\left\{ (a, b), (a, c),(b, d),(b, c),(d, e),(d, f),(f, g),(f, h),(f, i),(g, i)\right\}$. Используя вариант поиска в глубину, начиная с вершины $a$, с подсчётом функции $U p$, определить все мосты этого графа. Считать, что списки смежности упорядочены по алфавиту.

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

Обойти (занумеровать) вершины заданного неориентированного графа $\mathfrak {G}=(V, E)$ с помощью алгоритма обхода в глубину, начиная с вершины $a$, и построить дерево $\mathfrak {T}=(V, T)$ этого обхода. Граф задан списками смежности:

Какое обратное ребро $e \in E \backslash T$ и цикл в $\mathfrak {G}$ обнаружились в этом обходе первыми? Вычислить для каждой вершины $v$ значение $U p[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\}$.

Задан размеченный граф $\mathfrak {G}=(V, E)$, в котором $V=\left\{ a, b, c, d, e, f\right\}$, а длины рёбер заданы матрицей на рис. 14, «-» означает отсутствие ребра. Используя алгоритм Дейкстры, построить для $\mathfrak {G}$ дерево $\mathfrak {T}$ кратчайших путей из вершины $a$ во все остальные. Определить сумму длин всех рёбер дерева $\mathfrak {T}$.

Рис. 14: Матрица из задачи 379.

Дан ориентированный граф $\mathfrak {G}=(V, E)$, где $V=\left\{ a, b, c, d, e, f, g, h\right\} , E=\left\{ (a, b ; 3),(a, g ; 5),(b, a ; 4),(b, d ; 3),(b, h ; 2),(c, g ; 1), (c, h ; 6),(d, c ; 2),(d, e ; 4),(d, h ; 4),(e, c ; 12),(e, d ; 1),(f, c ; 12), (f, d ; 13),(f, g ; 15),(f, h ; 2),(h, a ; 5),(h, e ; 5)\right\}$ (третий элемент указывает вес соответствующего ребра). С помощью алгоритма Дейкстры по шагам найти кратчайшие пути из вершины $f$ во все остальные.

Дан ориентированный граф $\mathfrak {G}=(V, E)$, где $V=\left\{ a, b, c, d, e, f, g, h\right\} , E=\left\{ (a, e ; 11),(a, g ; 100),(b, f ; 46),(b, g ; 16), (c, e ; 71),(c, f ; 16),(c, g ; 111),(c, h ; 21),(d, a ; 8),(d, b ; 429), (d, h ; 3),(e, a ; 1),(e, g ; 25),(f, b ; 8),(g, b ; 2),(h, a ; 28),(h, b ; 154), (h, c ; 7),(h, d ; 9),(h, f ; 126)\right\}$ (третий элемент указывает вес соответствующего ребра). С помощью алгоритма Дейкстры по шагам найти кратчайшие пути из вершины $h$ во все остальные.

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

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

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

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