Определение. Деревом называется конечный связный граф с выделенной вершиной, именуемой корнем, не содержащий циклов.
Рис 2. Лес, имеющий две компоненты связности (2 дерева).
Будем далее обозначать через Х – множество вершин и U – множество ребер графа, а сам граф, определяемый этой парой объектов, будем обозначать <X,U>;
x ÎX, u ÎU. Обозначим длину дуги u=(x,y) через d(u). Кратчайшую длину пути из х в
z обозначим D(x,z).
Очевидно, если кратчайший путь из x в z существует и проходит через промежуточную вершину w, то D(x,z) = D(x,w) + D(w,z). Эта формула справедлива для любой промежуточной вершины w рассматриваемого пути, в том числе и для последней, смежной с конечной вершиной w. Поэтому кратчайший путь можно отыскать, последовательно переходя от конечной вершины z в ближайшую смежную и запоминая цепочку построенных вершин (конечно, при условии, что хотя бы один путь между вершинами x и z существует и граф не содержит циклов. Эта идея и является в сущности принципом Р.Беллмана.
1.2. Графовые алгоритмы
Алгоритм Беллмана поиска кратчайшего пути между двумя вершинами связного графа, не имеющего циклов с неотрицательными длинами ребер. Его описание приводится ниже при помощи алгоритмической схемы.
Идентификаторы :
D[w] – рабочий массив, при вычислениях интерпретируется как кратчайшая длина из вершины w в вершину z.
wÎX.
d[s,t] – массив длин ребер графа для каждой пары вершин s,t ÎX. Если некоторое ребро отсутствует, то в элементе этого массива полагается записанным некоторое достаточно большое число, превышающее сумму длин всех ребер графа.
Stack – последовательность вершин, определяющая кратчайший путь из x в z.
Begin
Stack:=’’; // Очистить Stack.
Stack <=z; // Поместить в стек конечную вершину z.
w:=z; // Запомнить первую пройденную вершину.
D[z]:=0; // Обнуление длины пути из вершины z в нее же.
While w=/=x do // Пока не будет достигнута начальная вершина, выполнять
// перебор вершин графа
p:= вершина, для которой величина D[p] = d[p,w]+D[w] минимальна. Если таких вершин несколько и среди них имеется вершина x, то p:=x, если же среди них нет вершины x – взять любую из доставляющих минимум сумме.
Stack <=p; // Записать выбранную вершину в стек.
w:=p; // и взять ее для построения следующего шага.
End;
End.
Пусть число вершин графа |X|=n, а число ребер |U|=m. Оценим сложность этого алгоритма как число шагов выполнения алгоритмической схемы, считая одним шагом выполнение ровно одного выполнимого оператора, каковые представлены только строками 2,3,4,5,6,8,9. В худшем случае выбор вершины в строке 8 (по минимуму расстояния) произойдет в результате просмотра всех n вершин, а цикл с заголовком в строке 6 повторится для всех вершин, поэтому сложность алгоритма можно оценить как C*n^2, где С – некоторая константа, учитывающая реализацию алгоритма в произвольной вычислительной среде.
Следующий алгоритм обеспечивает нахождение кратчайших расстояний от фиксированной вершины х, называемой источником, до всех остальных вершин графа с ограничением, предполагающим отсутствие в графе контуров отрицательной длины (сумма длин ребер, входящих в любой контур, неотрицательна).
Алгоритм Форда-Беллмана
Идентификаторы : d[s,t] – массив длин ребер графа для каждой пары вершин s,t ÎX. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число.
х – вершина-источник графа <X,U>.
n=|X| - число вершин графа.
u,w,k – рабочие переменные.
D[w] – массив, в котором к концу работы алгоритма будут содержаться кратчайшие длины путей из х в w для всех вершин w ÎX.
D[x]:=0; // Длина пути из источника x.
For w ÎX do D[w]:=d[x,w]; // Инициализация матрицы расстояний
For k:=1 to n-2 do // Повторять n-2 раз
For w Î{X\{x}} do // Цикл по всем вершинам, кроме источника.
For u ÎX do D[w]:=min(D[w],D[u]+d[u,w]); // выбор минимума.
Этот алгоритм также основан на соотношении (принципе оптимальности) Беллмана. Всякий раз, когда находится путь через транзитную вершину u, который короче найденного пути из х в w, он заменяется на более короткий путь. Это соотношение должно проверяться для любой возможной из n-2 транзитных вершин при оценке пути в каждую вершину, поэтому в алгоритме имеется цикл, определенный в строке 4.
Алгоритм Дейкстры нахождения кратчайших расстояний от источника до всех остальных вершин применим только тогда, когда граф не имеет контуров или когда веса всех ребер неотрицательны.
d[s,t] – массив длин ребер графа для каждой пары вершин
s,t ÎX. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число.
u,w – рабочие переменные.
D[w] – массив, в котором к концу работы алгоритма будут содержаться кратчайшие
длины путей из x в w для всех вершин w ÎX.
BEGIN
D[x]:=0;
For w ÎX do D[w]:=d[x,w];
T:={X\{x}};
While T=\= do
w:=вершина r из T такая, что D[r]=min{D[p]:p из T};
T:={T\{w}};
For u ÎT do D[w]:=min[D[w],D[u]+d[u,w]];
End
END
Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.
Многие задачи исследования операций сводятся к анализу потоков, маршрутов, последовательностей событий, протекающих со времени, и других процессов, которые можно представить в виде множества взаимосвязанных элементов. Для математического представления таких процессов удобно их задание в виде графов.
Рассмотрим конечный ориентированный граф Г=(X,u), в котором Х={x1,...,xn}-множество вершин, U – множество дуг.
Пусть x ÎX. Обозначим E+(x) – множество дуг графа, входящих в х, E-(x) – выходящих из х.
Множества начальных вершин дуг из Е+(х) и множество конечных вершин дуг из Е-(х) обозначим соответственно S+(x) и S-(x).
E+(x) E-(x)
S+(x) S-(x)
Рис. 3. Окрестность вершины графа.
Граф Г называют транспортной сетью, если каждой дуге u соответствует целое число c(u)>=0 и найдутся x0 и z из Х такие, что Е+(х0)=
Е-(z)= . Вершина х0 называется истоком, z-стоком, c(u) – пропускной способностью дуги. Потоком в транспортной сети называют целочисленную функцию ф(u), удовлетворяющую следующим условиям :
1) 0<=ф(u)<=с(u)
2) ф(u) - ф(u) = 0 для любой вершины x=/=x0, x=/=z.
u ÎЕ+(х) u ÎЕ-(х)
При этом поток не может «накапливаться» ни в одной вершине транспортной сети, кроме истока х0 и стока z, поэтому
ф(u) = ф(u) = Ф.
Величину Ф называют потоком транспортной сети. Дуга u называется насыщенной, если ф(u)=c(u). Поток Ф называется полным, если каждый путь из х0 в z содержит хотя бы одну насыщенную дугу.
Рассмотрим разбиение R множества вершин сети Х = Х1UX2,
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
