Взвешенные графы

Поиск расстояний

Граф называется взвешенным, если на множестве ребер определена весовая функция $\alpha$ во множество чисел.

Длиной пути $v_0, e_1, v_1, e_2, \ldots, e_k, v_k$ называется сумма $\sum\limits_{i=1}^k \alpha(e_i)$. Расстоянием $d(u, v)$ от вершины $u$ до вершины $v$ называется длина кратчайшего $(u,v)$-пути.

Определим функцию $a$ через $a(u,v) = \begin{cases} \alpha(e), & \text{если $e = (u,v) \in EG$},\\ \infty, & \text{если в $EG$ нет дуги $(u,v)$}. \end{cases}$

Будем искать значения $d(v_i) = d(v_0, v_i)$ для всех $v_i$, $i=1,\ldots,k$.

Алгоритм (Дейкстра): 1. (инициализация) для каждой вершины $v$ полагаем $d(v) = \infty$, $prev(v) = \text{NIL}$, $d(v_0) = 0$ 2. $S = \varnothing$, $Q = VG$ 3. пока $Q \neq \varnothing$ извлечем $u = \min Q$ и добавим $u$ в $S$ 4. (релаксация) для каждой $v \in N(u)$ если $d(v) > d(u) + a(u,v)$, то $d(v) = d(u) + a(u,v)$ и $prev(v) = u$

Для ручного применения: 1. полагаем $Q = V \setminus \{ v_0 \}$, и $d(v_i) = a(v_0, v_i)$ для всех $i=1,\ldots,k$

если $|Q| = 1$, то goto 5;
выбрать в $Q$ элемент $v$ для которого $d(v)$ является наименьшей
положим $Q = Q \setminus \{ v \}$, и $d(u) = \min \{ d(u), d(v)+a(v,u) \}$ для всех $u \in N(v) \cap S$, goto 2
выдать $d$

Док-во корректности.

Заметим, что если $d(v) \neq \infty$, то это длина некоторого $(v_0, v)$-пути.

Пусть на шаге 3 выбрана $v\in S$ и $d(v) \neq \infty$ и $v_0 = x_0, x_1, \ldots, x_n = v$ — кратчайший $(v_0,v)$-путь.

Покажем, что для всех $x_i$ этого пути $d(x_i) = d(v_0, x_i)$. Так для $x_0 = v_0$ это верно. Допустим, что $d(x_{i-1}) = d(v_0, x_{i-1})$, но $d(x_i) > d(v_0, x_i)$.

Тогда, поскольку $d(x_{i-1}) = d(v_0, x_{i-1}) < d(v_0, x_i) < d(x_i)$, то вершина $x_{i-1}$ выбиралась на шаге 3 раньше. На шаге 4 тогда $d(x_i)$ получило бы значение $d(x_{i-1}) + a(x_{i-1},x_i)$, которое равно $d(v_0, x_i)$. Противоречие.

Следовательно, для любой вершины $x_i$ выполняется $d(x_i) = d(v_0, x_i)$, в том числе $d(v) = d(v_0, v)$. Значит, что если существует $(v_0, v)$-путь, то на момент завершения алгоритма $d(v) = d(v_0, v)$.

Минимальный остов

Пусть $G$ - связный граф.

Остовом графа называется …

Алгоритм (Краскал):

$T_0 = \varnothing$, $Q = EG$
на $i$-ом шаге находим $e$ в $Q$ с минимальным весом и не образующее циклов с $T_{i-1}$
$T_i = T_{i-1} \cup \{ e \}$ и удаляем $e$ из $Q$
если $Q \neq \varnothing$ goto 2

Это жадный алгоритм.

Док-во корректности.

Множества ребер $T_i$ образуют ациклические графы с $i$ ребрами. Предположим, что остов $T_{n-1}$ имеет не минимальный вес среди всех остовов. Пусть $T_{\min}$ - остов меньшего веса, имеющий максимальное число общих с $T_{n-1}$ ребер. Найдем ребро $uv = e_i \in T_{n-1} \setminus T_{\min}$ с минимальным номером (шага добавления к $T_{n-1}$). В $T_{\min}$ есть $(u,v)$-цепь. Добавив к ней $e_i$ получим цикл, а удалив некоторое $e \notin T_{n-1}$ разомкнем цикл и получим остов $T_{\min}'$. Но $T_{\min}$ предполагался минимальным и значит $w(e_i) \geq w(e)$. С другой стороны, $e$ можно присоединить к $T_{i-1}$ не получив цикла. Следовательно, $w(e) = w(e_i)$, так как иначе на $i$-ом шаге выбрано было бы точно не $e_i$. Получается $w(T_{\min}) = w(T_{\min}')$ и $T_{\min}'$ тоже минимальный, но в нем на одно общее ребро с $T_{n-1}$ больше. Противоречие.