Минимальный путь в нагруженном ориентированном графе

Найти минимальный путь в нагруженном ориентированном графе из вершины в вершину по методу Форда-Беллмана.

Рассмотрим сначала общую задачу – нахождения минимального пути из вершины v_нач в v_кон.

Пусть D=(V,X) – нагруженный ориентированный граф, V={v₁,…,v_n}, n>1. Введем величины , где i=1,…,n, k=0,1,2,…,n–1.

Для каждого фиксированного i и k величина равна длине минимального пути среди путей из v_нач в v_i содержащих не более k дуг. Если путей нет, то .

Положим также .

Составляем матрицу длин дуг C(D)=[c_ij] порядка n:

Утверждение. При i=2,…,n, k³0 выполняется равенство

. (3.1)

Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе D из v_нач в v_кон.( v_нач ≠ v_кон).

( записываем в виде матрицы, i- строка, k-столбец).

1) Составляем таблицу , i=1,…,n, k=0,…,n-1. Если , то пути из v_нач в v_кон нет. Конец алгоритма.

2) Если то это число выражает длину любого минимального пути из v_нач в v_кон. Найдем минимальное k₁³1, при котором . По определению получим, что k₁- минимальное число дуг в пути среди всех минимальных путей из v_нач в v_кон.

3) Затем определяем номера i₂,…, такие, что

,

,

,

то есть восстанавливаем по составленной таблице и матрице стоимости искомый минимальный путь из v_нач в v_кон.

Пример

Найдем минимальный путь из вершины v₂ в v₆ в ориентированном нагруженном графе D, изображенном на рис. 9. В рассматриваемом графе количество вершин n=7, следовательно, матрица длин дуг ориентированного графа D будет иметь размерность 7×7.

Рис. 9.

Матрица длин дуг для рассматриваемого графа будет выглядеть следующим образом:

.

Согласно алгоритму, составляем таблицу стоимости минимальных путей из вершины v₂ в вершину v_i не более, чем за k шагов, k=0,…n-1 (n=7, следовательно, k=0,…6). Как было определено выше, , и для всех остальных вершин v_i ≠ v₂, то есть первый столбец таблицы состоит из элементов, равных , кроме элемента . Второй столбец таблицы повторяет вторую строку матрицы стоимости, поскольку представляет собой стоимость возможных путей из вершины v₂ за один шаг. Далее по формуле (3.1) находим по столбцам все оставшиеся элементы таблицы. Например, чтобы найти элемент , складываем элементы столбца и первого столбца матрицы стоимости и выбираем минимальное из получившихся чисел: .

В конечном итоге получаем следующую таблицу:

Теперь необходимо по построенной таблице и по матрице C(D) восстановить минимальный путь из вершины v₂ в v₆, который будет строиться с конца, то есть, начиная с вершины v6. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v₆ в таблице. Это число – 21 – длина минимального искомого пути. В первый раз такая длина была получена при количестве шагов, равном 4. В вершину v₆ мы можем попасть за один шаг из вершин v₁ и v₇ (длина соответствующих дуг 8 и 5 соответственно – данные из матрицы C(D)). Выбираем минимальную по длине из этих дуг. Далее, в вершину v₇ можно попасть из v₄ и v₅(длина соответствующих дуг 7 и 3 соответственно). Продолжая аналогичным образом, найдем искомый путь за 4 шага минимальной длины из вершины v₂ в v₆: v₂ v₃ v₅ v₇ v₆.

Деревья

Определение 1

Граф без циклов (ациклический граф) называется лесом.

Определение 2

Связный ациклический граф называется деревом.   Теорема 3 Для (n, m) - графа G следующие утверждения эквивалентны: 1) G-дерево; 2) G-связный граф и m= n – 1; 3) G-ациклический граф и m= n – 1; 4) любые две несовпадающие вершины графа G соединены единственной простой цепью. Доказательство   1) Þ 2) Пусть дан (n,m) граф G – связный и ациклический. Докажем индукцией по n, что m= n – 1. Базис индукции: n=1, m=0; Индуктивное предположение: допустим при n < k m=n-1; Индуктивный переход: докажем, что при n=k m=n-1. Удалив ребро, получим два дерева с числом вершин Очевидно . По индуктивному предположению Вернув ребро, получим 2) Þ 3) Пусть дан связный (n, m) граф G и m=n–1. Докажем, что G – ациклический граф. Предположим противное: в G существует цикл и пусть - ребро этого цикла. Тогда граф - связный по теореме 7 предыдущего параграфа и имеет ребра, что невозможно по теореме 9 предыдущего параграфа. Значит, граф G – ациклический. 3) Þ 4) Пусть дан ациклический (n, m)-граф G и m= n–1. Докажем, что любые две несовпадающие вершины графа G соединены единственной простой цепью. Предположим противное: пусть существуют вершины u и v, которые можно соединить по крайней мере двумя различными простыми цепями: u x1 x2 … xk v и u y1 y2 … ys v. Но тогда в графе есть цикл u x1 x2 … xk v ys … y1 y2 u, что противоречит пункту 3). Значит, любые две несовпадающие вершины графа G соединены единственной простой цепью. 4) Þ 1) Пусть любые несовпадающие вершины графа G соединены единственной простой цепью. Значит граф G – связный. Покажем, что в графе G нет циклов. Предположим противное: пусть в графе G существует цикл. Тогда любые две вершины этого цикла можно соединить по крайне мере двумя различными простыми цепями, что противоречит пункту 4). Значит, граф G – ациклический.   Теорема 4 В любом дереве порядка n³2 имеется не менее двух висячих вершин. Доказательство   Для дерева порядка n справедливо равенство (1) Допустим противное: в дереве порядка n³2 либо нет висячих вершин, либо ровно одна висячая вершина. В первом случае степень каждой вершины не меньше двух, следовательно . Во втором случае степень висячей вершины равна 1, а остальных не меньше 2, следовательно Оба неравенства противоречат равенству (1).

Определение 5

Висячая вершина дерева называется концевой вершиной. Теорема 6 Центр любого дерева состоит из одной или из двух смежных вершин. Доказательство Заметим, сперва, что концевые вершины дерева будут центральными, только если T=K1 или Т=K2. Рассмотрим дерево Т с n вершинами (n > 2) и удалим его все концевые вершины. Получим дерево, у которого центр будет тот же самый, что у дерева Т, а радиус – на единицу меньше, чем у дерева Т. Таким образом, проделав процедуру удаления всех концевых вершин некоторое число раз, мы получим или граф K1 или граф K2. Так как центр при этом не изменится, то центр произвольного дерева Т совпадет с центром графа K1 или с центром графа K2, т.е. будет состоять из двух смежных вершин, как у K2, или из одной, как у K1.

Определение 7

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

Определение 8

Граф G = (V, E) будем называть взвешенным, если существует функция f: E®R, т.е. каждому ребру графа G поставлено в соответствие некоторое вещественное число, которое называется весом (стоимостью, длиной) ребра.

Определение 9

Если остовный подграф некоторого графа является деревом, то будем называть его остовным деревом или остовом Алгоритм Краскала (алгоритм нахождения во взвешенном графе остова наибольшего или наименьшего веса).   Пусть дан связный взвешенный граф G = (V, E), çV ê= n. Цель: построение дерева Т наименьшего (наибольшего) веса являющегося остовом графа G: 0 шаг: в качестве искомого берем Т=Оn 1 шаг: выберем в G ребро наименьшего (наибольшего) веса и добавим его в Т. i шаг (к тому моменту граф Т содержит уже (i–1) ребро графа G): выбираем из оставшихся ребер графа G ребро наименьшего (наибольшего) веса, не образующий циклов с уже выбранными ребрами, и добавим его в Т. Критерий останова: алгоритм прекращает свою работу, когда уже выбрано (n–1) ребро, так как в этом случае добавление любого оставшегося ребра будет приводить к образованию цикла. Пример - остов минимального веса, – остов максимального веса.

Двудольные графы

Определение 1

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

Определение 2

Двудольный граф называется полным двудольным, если любые две его вершины, принадлежащие разным долям, смежны. Обозначают: – полный двудольный граф, где в одной доле n, а в другой доле m вершин.   Пример

Определение 3

Граф вида называется звездой порядка n. Пример

Определение 4

Граф называется k-дольным, если множество его вершин можно разделить на k долей так, чтобы концы любого ребра принадлежали разным долям. Пример   Теорема 5 (Кёнига, критерий двудольности графа) Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.   Доказательство   Необходимость. Пусть двудольный граф содержит цикл длины k. Докажем, что k – четное число. Концы всех его ребер принадлежат разным долям, поэтому, проходя по циклу, мы каждый раз попадаем из одной доли в другую. На последнем шаге мы возвращаемся в исходную вершину, а значит, делаем четное число таких «переходов», поэтому k – четное число. Достаточность. Пусть граф G не содержит циклов нечетной длины, то есть все имеющиеся в нем циклы четной длины. Разделим все вершины графа G на две части. В первую часть попадут все вершины, расстояние до которых от фиксированной вершины v четное число, и сама вершина v, а во вторую – все остальные вершины. Осталось показать, что никакие две вершины, попавшие в один класс не смежны. Предположим противное, то есть некоторые вершины x и y, принадлежащие одному из двух полученных множеств, смежны. Рассмотрим цикл, полученный в результате объединения ребра (x; y) и кратчайших цепей, соединяющих вершины x и y с вершиной v. Длина этого цикла равна сумме длин этих двух цепей плюс один. Но длины этих двух цепей одинаковой четности, поэтому их сумма – четное число, значит длина получившегося цикла – нечетное число. Пришли к противоречию, значит никакие две вершины, попавшие с один класс, не смежны.     Следствие 6   Граф является двудольным тогда и только тогда, когда он не содержит простых циклов нечетной длины.     Алгоритм поиска в ширину   Выбираем произвольную вершину в графе и приписываем ей номер ноль. Всем вершинам из ее окружения приписываем номер один. Далее рассматриваем поочередно окружение всех вершин с номером один и еще не занумерованным вершинам приписываем номер два, и так далее, пока это возможно. Если граф G связен, то поиск в ширину занумерует все его вершины. Далее разобьем множество вершин на две части , отнеся к все вершины с четными номерами, а к - все остальные. Если среди вершин множества нет смежных и среди вершин множества нет смежных (достаточно проверить все пары вершин с одинаковыми номерами), то граф G – двудольный.   Примеры Граф G не является двудольным Граф H – двудольный.   Алгоритм поиска в ширину позволяет решать следующие задачи. 1) Поиск кратчайшей цепи, соединяющей две несовпадающие вершины. 2) Разбиение множество вершин графа на области связности. 3) Поиск в ориентированном графе всех вершин, достигаемых из заданной вершины. Пример Незанумерованная вершина недостижима из вершины с номером ноль.