4.2.3.Другие важные экстремальные задачи на графах
Кратчайшие пути
Пусть ‑ ориентированный взвешенный граф. Задача о кратчайшем пути [6] состоит в отыскании пути минимального веса, соединяющего заданные начальную и конечную вершины графа при условии, что хотя бы один такой путь существует. Начальную и конечную вершины обозначим соответственно через и;-путь минимального веса будем называть кратчайшим-путем.
Вначале рассмотрим случай, когда веса всех дуг графа неотрицательны, т. е. для каждой дуги.
В этом случае решение задачи о кратчайшем пути является существенно менее трудоемким, чем в общем случае. Первый эффективный алгоритм построения кратчайшего пути в графе с неотрицательными весами дуг предложил Е. Дийкстра в 1959 г.
На каждой итерации этого алгоритма всякая вершина графаполучает метку, которая может быть постоянной либо временной. В первом случаевес кратчайшего-пути. Если же меткавременная, то‑ вес кратчайшего-пути, проходящего только через вершины с постоянными метками. Таким образом, временная меткаявляется оценкой сверху для веса кратчайшего-пути, и став на некоторой итерации постоянной, она остается такой до конца работы алгоритма. Кроме, с каждой вершинойграфа, за исключением, связывается еще одна метка ‑. На каждой итерацииявляется номером вершины, предшествующейв-пути, имеющем минимальный вес среди всех-путей, проходящих через вершины, получившие к данному моменту постоянные метки. После того как вершинаполучила постоянную метку, с помощью метоклегко указать последовательность вершин, составляющих кратчайший-путь.
Перед началом первой итерации алгоритма вершина имеет постоянную метку, а меткивсех остальных вершин равныи эти метки временные. Общая итерация алгоритма состоит в следующем. Пусть‑ вершина, получившая постоянную меткуна предыдущей итерации. Просматриваем все вершины, имеющие временные метки, с целью уменьшения (если это возможно) этих меток. Меткавершинызаменяется на, если оказалось, что. в этом случае говорим, что вершинаполучила свою меткуиз вершины, и полагаем. Если же, то метки и вершиныне изменяются на данной итерации. Алгоритм заканчивает работу, когда меткастановится постоянной. Как уже говорилось выше,‑ вес кратчайшего-пути, который будем обозначать через. Этот путь определяется с помощью меток так:
,
где для любой вершины.
Вопросы
Сформулируйте задачу о минимальном остове графа и алгоритм построения остовного дерева минимального веса, предложенный Примом.
ЗАДАЧИ
Задание. Найти минимальный остов полного графа с помощью алгоритма Прима. Наборы коэффициентов заданы в таблице 4.1.
Варианты заданий
Таблица 4.1
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16
|
17 |
18 |
19
|
20 |
a1 a2 a3 a4 a5 |
3 4 3 4 2 |
4 5 4 3 2 |
1 2 3 2 1 |
4 5 4 3 5 |
5 4 3 5 4 |
4 5 6 5 4 |
3 4 3 4 3 |
5 4 6 7 8 |
5 6 7 6 7 |
2 3 1 3 3 |
6 5 6 5 7 |
2 2 2 3 3 |
5 4 5 4 3 |
4 5 6 5 6 |
4 5 6 7 8 |
6 6 6 7 7 |
3 4 5 5 6 |
4 5 6 7 4 |
5 6 4 5 6 |
8 7 8 6 5 |
b1 b2 b3 b4 b5 |
2 3 4 2 4 |
4 3 2 2 3 |
3 4 3 2 1 |
6 7 5 6 4 |
3 4 3 3 2 |
6 7 5 4 6 |
4 5 6 7 5 |
3 4 5 6 4 |
6 7 8 9 7 |
3 4 5 4 3 |
6 5 4 4 4 |
4 4 6 7 8 |
6 7 8 7 6 |
8 9 7 8 6 |
7 6 7 5 5 |
5 6 6 7 1 |
3 4 7 8 5 |
6 5 7 8 4 |
6 6 5 5 4 |
8 7 9 8 7 |
d1 d2 d3 d4 d5 |
4 3 2 3 3 |
2 2 2 3 3 |
4 3 2 2 2 |
2 2 3 4 3 |
3 3 3 2 2 |
1 2 3 1 2 |
3 4 3 3 2 |
1 2 1 2 3 |
3 4 2 5 4 |
1 1 2 2 3 |
3 3 2 4 3 |
3 4 3 2 3 |
2 3 4 3 4 |
4 3 2 3 4 |
4 3 2 3 2 |
2 3 2 4 4 |
4 3 1 2 3 |
3 3 4 2 2 |
1 2 3 4 2 |
4 3 4 2 2 |
1Заметим, что в определении отсутствует случай, когда в вершинеимеется петля. Часто используется дополнительное значение для(например, какой-нибудь символ или выражение «1 и -1»).
2Более общим по сравнению с ХГ является класс совершенных графов [34]. Граф называется совершенным, если для каждого порожденного графаграфавыполняется равенство. Задачи поиска такихграфовых параметров, какдля совершенных графов являются полиномиальными (т.е. разрешимыми за полиномиальное время).
3Правда, этот метод столь же неэффективен, как и другие методы установления изоморфизма двух произвольных графов.
4Иногда нумерация понимается в более широком смысле. Это либо векторная нумерация , т.е. отображение вида(), либо отображение множества вершин в некоторое множество объектов нечисловой природы, например в множество символов некоторого алфавита, множество слов и т. д.
5Название «поиск в глубину» (в англоязычной литературе ‑depthfirstsearch(DFS)) связано с тем, что при выполнении обхода графа по этим правилам мы стремимся проникнуть в глубь графа так далеко, как это возможно, затем отступаем на шаг назад и снова стремимся пройти вперед и так далее.
6 DFS = depth first search (поиск в глубину).
7Как известно, матрицыи, удовлетворяющие условию (4.3), называютсяподобными. Разработаны алгебраические методы, позволяющие решить вопрос о подобии матрици. Представляется целесообразной попытка соединения алгебраических методов и описанных здесь подходов.
8Зыков А. А. Теория конечных графов. — Новосибирск: Наука, 1969.
9 Appel K., Haken W. Every planar map is four colorable: Part I: Discharging // Illinois J. Math. ‑1977. ‑21. ‑P. 429-490.
10Зыков А. А. Теория конечных графов. — Новосибирск: Наука, 1969.
11Так что с точки зрения сложности задача о минимальном остове действительно является легкой.