Предварительные сведения.

Что такое граф?

Часто в задачах встречается следующая конструкция - есть дома и дороги, их соединяющие; у каждой дороги есть длина. По другой терминологии такая конструкция называется графом, дома называются "вершинами", дороги - "ребрами" или "дугами", а длина дороги "весом ребра" или "весом дуги". Таким образом фраза 'Найти минимальный вес пути между вершинами s и k в графе' может быть переведена так: 'Есть дома и дороги их соединяющие. Также заданы длины дорог. Найти кратчайшую длину пути от города s до города k, если двигаться можно только по дорогам'. Пропускная способность дуги (i,j) означает, например, сколько груза может быть перевезено по дороге (по дуге) (i,j) за единицу времени); а поток по дуге (i,j) -- это сколько перевозится сейчас на самом деле).

Часто используют следующие обозначения: Г(x(i))- множество вершин, в которые есть дуга из вершины i; Д(x(i))- множество вершин, из которых есть дуга в вершину i.

Пусть в графе N вершин.

Длины дуг обычно заносятся в матрицу (назовем ее C) размера N на N, называемой матрицей смежности:



Элемент 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) - это пропускная способность дуги (т.е., например, сколько груза может быть перевезено по дороге (по дуге) (i,j) за единицу времени); q(i,j) - поток по дуге (i,j) (т.е. сколько перевозится сейчас на самом деле).


Кратчайшее расстояние от вершины нач до остальных вершин (Алгоритм Дейкстры).

Обозначения:

C[i,j]- длина ребра(i,j), С[i,j]>=0 (если ребра нет, то его длина полагается равной бесконечности).

D[i]- кратчайшее текущее расстояние от вершины нач до вершины i.

флаг[i]- информация о просмотре вершины i: 0 - если вершина не просмотрена, 1 - если просмотрена. Если вершина просмотрена, то для нее D[i] есть наикратчайшее расстояние от вершины нач до вершины i.

предок[i]- информация о номере вершины, предшествующей вершине i в кратчайшем пути от вершины нач.

минрас - это минимальное расстояние.

Алгоритм:

для i от 1 до N выполнять
нц
предок[i]:=нач;
флаг[i]:=0;
D[i]:=C[нач,i]
кц
флаг[нач]:=1; {пока мы знаем только расстояние}
предок[нач]:=0 {от вершины нач до нее же, равное 0}
для i от 1 до N-1 выполнять
нц
минрас:=бесконечность;
для j от 1 до N выполнять
если (флаг[j]=0 и (минрас > D[j]) {находим минимальное}
то минрас:=D[j]; {расстояние}
k:=j; {до непомеченных вершин}
все
флаг[k]:=1; {вершина k помечается просмотренной}
для j от 1 до N выполнять {выполняем просмотр}
если флаг[j]=0 и D[j]>D[k]+C[k,j]
{Т.е. если для вершины j еще не найдено кратчайшее расстояние
от нач, и из вершины k по дуге C[k,j] путь в j короче,
чем найденный ранее}
то D[j]:=D[k]+C[k,j] {то запоминаем его}
предок[j]:=k;
все
кц

---

А вот задача для примера и её алгоритм решения...

---

Задан набор неповторяющихся пар (Ai,Aj), Ai, Aj принадлежат множеству А={A1, A2, ..., An}. Необходимо составить цепочку максимальной длины по правилу

(Ai,Aj)+(Aj,Ak)=(Ai,Aj,Ak).

При образовании этой цепочки любая пара может быть использована не более одного раза.

Решение задачи 1.

Для более удобного хранения информации заведем матрицу

C[1...n,1..n] (так называемую матрицу смежности) в которой C[i,j]=1, если в наборе есть пара (Ai,Aj)
и C[i,j]=0 иначе.

Будем строить все возможные цепочки (по правилу, данному в условии) и искать среди них ту, которая имеет
максимальную длину.

В качестве начального символа цепочки можно взять любой символ из A. Пусть это символ Ai. Ищем, просматривая
строку i матрицы C слева направо элемент C[i,j]=1 (другими словами, ищем пару с первым элементом Ai). Если такого
элемента не существует, то берем в качестве начала строки другой элемент множества A. Если элемент C[i,j]=1
найден, то ему соответствует пара (Ai,Aj). Помечаем ее как уже использованную полагая, например, C[i,j]=-1. Далее
просматриваем слева направо строку j матрицы C в поисках еще не использованной пары (Aj,Ak) (C[j,k]=1).
Присоединяем элемент Ak к имеющейся цепочке, полагаем C[j,k]=-1, ищем единичный элемент в строке k и т.д.
Предположим, на некотором шаге мы получили цепочку

Ai Aj Ak ... As Al Ap

и в строке p матрицы больше нет ни одного единичного элемента. Это означает, что при таком подборе предыдущих
элементов мы нашли максимальную по длине строку. Если ее длина больше длин всех найденных ранее строк, запоминаем
эту строку как рекорд. После этого "отщепляем" от строки последний элемент Ap и смотрим, есть ли еще в строке l
единичный элемент с индексом, большим p. Если да, то приписываем уже этот элемент к строке и пытаемся затем снова
увеличить длину полученной строки, если же нет, то "отщепляем" от строки элемент A1, в строке S ищем единичный
элемент с индексом, большим l и т.д.

Останов осуществляется тогда, когда мы должны "отщепить" от строки Ai.

Перебираем цепочки, начинающиеся со всех возможных элементов множества A. Находим строку максимальной длины:

---