|
Лекция 11
Взвешенный
граф. Кратчайшие пути во взвешенном графе и алгоритм Форда построения
кратчайших маршрутов.
Граф  называется взвешенным, если определена любая
функция  (функция на множестве
ребер со значениями во множестве вещественных чисел). Сама функция  называется в этой
ситуации весовой, а ее значение на
том или ином ребре называется весом
этого ребра. Любой подграф данного графа и любой путь в данном графе имеют свой вес: это - сумма весов ребер,
входящих в этот подграф или в этот путь.
На взвешенном графе с весовой функцией можно ввести понятие расстояния между вершинами. Делается это
так.
Будем
считать далее, если не будет специальных оговорок, что все рассматриваемые
графы связны. Вес любого пути будем называть длиной этого пути. Ясно, что
между двумя вершинами существует такой путь, который имеет минимальную
возможную длину. Эта длина и называется расстоянием
между двумя вершинами. Путь, который эту длину реализует, естественно,
называется кратчайшим.
Существует
классический алгоритм Форда поиска
кратчайших путей в графе. Основан он на следующем простом факте: если имеется кратчайший путь между
какими-либо двумя вершинами, то его часть между любыми двумя вершинами на нем
же самом также является кратчайшим путем.
Алгоритм Форда позволяет найти кратчайшие
пути из какой-либо одной вершины графа во все остальные. Эту исходную вершину
можно выбрать произвольно, но, сделав выбор, далее уже исходить из того, что
будут описаны кратчайшие пути именно из этой вершины во все остальные.
Опишем алгоритм по шагам.
Шаг 0. Занумеруем все вершины
из , так что  и при этом номер «1»
имеет именно та вершина, из которой будут найдены кратчайшие пути во все
остальные вершины. Построим, далее матрицу  , положив
Шаг 1. Около первой строки матрицы  , слева от матрицы, поставим числовую пометку «0» и такую же
пометку проставим над первым столбцом матрицы. Затем просмотрим помеченную
строку слева направо и всякий раз, встречая клетку с числом, прибавим это число
к пометке строки и сумму проставим над столбцом, в котором эта клетка
находится.
Затем отразим пометки столбцов
относительно главной диагонали. Возникнут помеченные строки. С каждой из
помеченных строк проделаем то же самое: просмотрим помеченную строку слева
направо и всякий раз, встречая клетку с числом, прибавим это число к пометке
строки и сумму поставим в качестве пометки над столбцом, в котором эта клетка
стоит. При этом будем соблюдать принцип Ã: «имеющуюся пометку не менять».
Затем пометки столбцов отразим
относительно главной диагонали и с помеченными строками вновь проделаем то же
самое. И так далее, пока не окажутся помеченными все строки и все столбцы.
Шаг 2. Просмотрим строки
таблицы в порядке возрастания их номеров. В каждой строке просматриваются
клетки слева направо и всякий раз, когда встречается число, оно складывается с
пометкой строки и сумма сравнивается с пометкой столбца, в котором найденное
число расположено. Если сумма оказалась меньше, чем пометка столбца, то эта
пометка столбца заменяется на упомянутую сумму. Если же сумма оказалась больше
или равной пометке, то ничего не меняется.
После такого просмотра всех строк
новые пометки столбцов отражаются относительно главной диагонали и вся
процедура повторяется. И так до тех пор пока не прекратятся какие бы то ни было
изменения в пометках.
Шаг 3. Теперь по пометкам
можно построить кратчайшие пути из первой вершины во все остальные. Фиксируем
произвольную вершину  и опишем кратчайший
путь из первой вершины в вершину  . Во-первых, длина этого кратчайшего пути равна помет-
ке  , стоящей над столбцом номер . Во-вторых, предпоследняя
вершина в кратчайшем пути из первой вершины в вершину находится так: в
столбце номер отыскиваем число,
сумма которого с пометкой строки, в которой оно расположено, равна . Пусть номер строки, в которой найденное число оказалось,
равен  . Тогда предпоследней вершиной в кратчайшем пути из 1 в будет вершина . (Разумеется, всё только что сказанное нуждается в
доказательствах,
которые не
приводятся.) Вершину, которая предшествует вершине , надо отыскивать как предпоследнюю в кратчайшем пути из 1 в и так далее.
Приведем пример. Пусть исходный
взвешенный граф дает следующую матрицу :
Начнем
расставлять пометки:
Проведем
уменьшение пометок:
Укажем
кратчайшие пути:
1Þ2: длина 10; путь (от конца к началу) 2Ü1;
1Þ3: длина 13; путь (от конца к началу) 3Ü1;
1Þ4: длина 30; путь (от конца к началу) 4Ü 3Ü1;
1Þ5: длина 23; путь (от конца к началу) 5Ü3Ü1;
1Þ6: длина 34; путь (от конца к началу) 6Ü7Ü2Ü1;
1Þ7: длина 21; путь (от конца к началу) 7Ü2Ü1;
1Þ8: длина 38; путь (от конца к началу) 8Ü5Ü3Ü1.
Лекция 12
Остов
в графе и алгоритм Краскала поиска остова минимального веса во взвешенном
графе.
Пусть - граф и - весовая функция. Как
обычно, предполагается, что все рассматриваемые графы связны. Остовом графа, напомним, называется
подграф, являющийся деревом и содержащий все вершины данного графа. Нетрудно
доказать, что в каждом графе обязательно есть остов.
Как определялось ранее, вес подграфа - это сумма весов его
ребер. Ясно, что во взвешенном графе существует остов наименьшего веса.
Существует алгоритм Краскала, позволяющий найти остов минимального веса в
любом взвешенном графе. Дадим его описание по шагам.
Шаг 1. Найдем в данном графе
ребро минимального веса (если таких несколько, фиксируем любое). Обозначим его
через  ; кроме того, фиксируем подграф в данном графе  , состоящий из концов ребра и самого этого ребра.
Обозначим этот подграф через  .
Шаг 2. Фиксируем в данном
исходном графе второе ребро -
обозначим его через  , - вес которого минимален относительно весов всех ребер, не
принадлежащих . Подграф, состоящий из ребер , и их концов обозначим
через  .
Шаг 3. Фиксируем в графе ребро - обозначим его
через  , - имеющее минимальный вес среди всех ребер графа , не принадлежащих , и не составляющих цикла с ребрами из . Подграф, состоящий из ребер , , и их концов, обозначим
через  .
Шаг 4. Фиксируем в графе ребро - обозначим его
через  , - имеющее минимальный вес среди тех ребер графа , которые не принадлежат и не образуют цикла с
ребрами из . Подграф, состоящий из ребер
, , , и их концов обозначим
через  .
Общий шаг - шаг № k.
Фиксируем в графе ребро – обозначим его
через  , - имеющее минимальный вес среди ребер, не входящих в  и не составляющих
цикла с ребрами из . Подграф, состоящий из ребер , , ,..., , обозначим через  .
Можно доказать, что если в исходном графе количество вершин равно  , то подграф  будет искомым остовом.
|
