|
Что такое граф?
Часто в задачах
встречается следующая конструкция - есть дома и дороги, их соединяющие;
у каждой дороги есть длина. По другой терминологии такая конструкция
называется графом, дома называются "вершинами", дороги - "ребрами" или
"дугами", а длина дороги "весом ребра" или "весом дуги". Таким образом,
фраза 'Найти минимальный вес пути между вершинами s и k в графе' может
быть переведена так: 'Есть дома и дороги их соединяющие. Также заданы
длины дорог. Найти кратчайшую длину пути от города s до города k, если
двигаться можно только по дорогам'. Пропускная способность дуги (i,j)
означает, например, сколько груза может быть перевезено по дороге (по
дуге) (i,j) за единицу времени); а поток по дуге (i,j) - это сколько
перевозится сейчас на самом деле).
Часто используют следующие обозначения: Г(x(i))- множество вершин, в которые есть дуга из вершины i; Д(x(i))- множество вершин, из которых есть дуга в вершину i.
Пусть в графе N вершин.
Длины дуг обычно заносятся в матрицу (назовем ее C) размера N на N, называемой матрицей смежности:
var С: array [1..N,1..N] of integer;
Элемент C[i,j] этой матрицы равен длине дуги (дороги), соединяющей вершины i и j, и равен (например) 0 или -1, если такой дуги нет. Если дорога двунаправленная (дуга неориентированная), то очевидно, что C[i,j]=C[j,i].
Задача о максимальном потоке.
Алгоритм расстановки пометок для задачи о максимальном (от s к t) потоке:
А.Расстановка пометок. Вершина может находиться в одном из трех состояний:
- вершине приписана пометка, и вершина просмотрена (т.е. она имеет пометку и все смежные с ней вершины "обработаны"),
- пометка приписана, но вершина не просмотрена (т.е. она имеет пометку, но не все смежные с ней вершины обработаны),
- вершина не имеет пометки.
Пометка произвольной вершины x(i) состоит из двух частей и имеет один из двух видов: (+x(j),m) или (-x(j),m). Часть +x(j) пометки первого типа означает, что поток допускает увеличение вдоль дуги (x(j),x(i)). Часть -x(j) пометки другого типа означает, что поток может быть уменьшен вдоль дуги (x(i),x(j)). В обоих случаях m задает максимальную величину дополнительного потока, который может протекать от s к x(i) вдоль построенной увеличивающей цепи потока. Присвоение пометки вершине x(i) соответствует нахождению увеличивающей цепи потока от s к x(i). Сначала все вершины не имеют пометок.
Шаг 1. Присвоить вершине s пометку (+s,m(s)=бесконечность). Вершине s присвоена пометка, и она просмотрена, все остальные вершины без пометок.
Шаг 2. Взять некоторую не просмотренную вершину с пометкой; пусть ее пометка будет (+-x(k),m(x(i))) (+- обозначает, что перед x(k) может стоять как плюс, так и минус).
(I) Каждой помеченной вершине x(j), принадлежащей Г(x(i)), для которой c(i,j)<q(i,j), присвоить пометку (-x(i),m(x(j))), где m(x(j))=min[m(x(i)),q(i,j)-c(i,j)].
(II) Каждой непомеченной вершине x(j), принадлежащей Д(x), для которой c(i,j)>0, присвоить пометку (-x(i),m(x(j))), где
m(x(j))=min[m(x(i)),c(j,i)].
(Теперь вершина x(i) и помечена, и просмотрена, а вершины x(j), пометки которым присвоены в (I) и (II), являются непросмотренными.) Обозначить каким-либо способом, что вершина x(i) просмотрена.
Шаг 3. Повторять шаг 2 до тех пор, пока либо вершина t будет помечена, и тогда перейти к шагу 4, либо t будет не помечена и никаких других пометок нельзя будет расставить; в этом случае алгоритм заканчивает работу с максимальным вектором потока c. Здесь следует отметить, что если X(0)-множество помеченных вершин, а X'(0) - множество не помеченных, то ( X(0) --> X'(0)) является минимальным разрезом.
Б. Увеличение потока.
Шаг 4. Положить x=t и перейти к шагу 5.
Шаг 5.
(I) Если пометка в вершине x имеет вид (+z,m(x)), то изменить поток вдоль дуги (z,x) c c(z,x) на c(z,x)+m(t).
(II) Если пометка в вершине x имеет вид (-x,z) c c(x,z) на c(x,z)-m(t).
Шаг 6. Если z=s, то стереть все пометки и вернуться к шагу 1, чтобы начать расставлять пометки, но используя уже улучшенный поток, найденный на шаге 5. Если z<>s, то взять x=z и вернуть к шагу 5.
Обозначения: Г(x(i))- множество вершин, в которые есть дуга из вершины i;
Д(x(i))- множество вершин, из которых есть дуга в вершину i;
c(i,j) - это пропускная способность дуги;
q(i,j) - поток по дуге (i,j).
На сегодня все! |