2.1. Алгоритм расстановки пометок для задачи о максимальном (от s к t) потоке

А. Расстановка пометок.

Вершина может находиться в одном из трех состояний: вершине приписана пометка и вершина просмотрена (т. е. она имеет пометку и все смежные с ней вершины

«обработаны»), пометка приписана, но вершина не просмотрена (т. е. она имеет пометку, но не все смежные с ней вершины обработаны), вершина не имеет пометки. Пометка произвольной вершины я; состоит из двух частей и имеет один из двух видов: или Часть пометки первого типа означает, что поток допускает увеличение вдоль дуги Часть пометки другого типа означает, что поток может быть уменьшен вдоль дуги В обоих случаях задает максимальную величину дополнительного потока, который может протекать от вдоль построенной аугментальной цепи потока. Присвоение пометки вершине соответствует нахождению аугментальной цепи потока от Сначала все вершины не имеют пометок.

Шаг 1. Присвоить вершине пометку Вершине присвоена пометка и она просмотрена, все остальные вершины без пометок.

Шаг 2. Взять некоторую непросмотренную вершину с пометкой; пусть ее пометка будет Каждой непомеченной вершине для которой присвоить пометку где

(II) Каждой непомеченной вершине для которой присвоить пометку где

(Теперь вершина и помечена, и просмотрена, а вершины пометки которым присвоены в (I) и являются непросмотренными.) Обозначить каким-либо способом, что вершина просмотрена.

Шаг 3. Повторять шаг 2 до тех пор, пока либо вершина будет помечена, и тогда перейти к шагу 4, либо будет не помечена и никаких других пометок нельзя будет расставить; в этом случае алгоритм заканчивает работу с максимальным вектором потока Здесь следует отметить, что если множество помеченных вершин, а множество не помеченных, то является минимальным разрезом.

Б. Увеличение потока

Шаг 4. Положить и перейти к шагу 5.

Шаг 5. (I) Если пометка в вершине х имеет вид то изменить поток вдоль дуги на .

(II) Если пометка в вершине х имеет вид то изменить поток вдоль дуги на

Шаг 6. Если то стереть все пометки и вернуться к шагу 1, чтобы вновь начать расставлять пометки, но используя уже улучшенный поток, найденный на шаге 5. Если то взять и вернуться к шагу 5.