Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 19

Для поиска распределения потока по дугам графа разработано несколько алгоритмов, особое место среди которых занимает алгоритм Форда-Фалкерсона, суть которого состоит в разметке вершин графа. Метка вершины графа указывает на возможность изменения потока через данную вершину и указывает источник этого изменения. На рис. 33 дан фрагмент сети, объясняющий суть алгоритма.

Если по дуге (хs, хi) возможно увеличение потока, т.е. j si< csi, то вершину хi следует пометить +s  , что указывает на источник увеличения потока. Если по дуге (хi, хj) возможно увеличение потока j ij< cij, то вершину хj пометить +i . Это означает, что приращение потока  Djsi пойдет по направлению дуги (хi, хj) от вершины хs.

Если по дуге (хt, хj) возможно увеличение потока, т.е. j tj< ctj, то вершину хj следует пометить +t , что указывает на источник увеличения потока. Однако, если вершина хj не имеет пометки +i  , то для увеличения потока в фрагменте сети, следует уменьшить поток в дуге (хi, хj) и направить его далее по другим дугам фрагмента на сток. Для указания вершины, от которой необходимо уменьшить поток, ставят пометку –j  . Это означает что на участке (хi, хj) поток должен быть уменьшен на величину  Djtj.

Следует отметить, что вершины хi и хj могут иметь одновременно по нескольку подходящих и отходящих дуг. В примере, показанном на рис. 33 одновременно при допустимых  Dj si и Dj tj могут быть  для вершины хj две метки +t   и   +i  для вершины хi также две метки   +s   и   -j , что свидетельствует о свободе выбора приращения потока либо на величину Dj si, либо  Dj tj.

 Если дуга (хs, хi) насыщена, т.е. j si=csi, то метку  +s  у вершины хi ставить нельзя. Если насыщена дуга (хt, хj), т.е. j tj=ctj, то метку  +t   у вершины хj ставить нельзя.

Если вершина хj не помечена, то нельзя ставить метку   -j   у вершины хi. Когда обе вершины графа (хi и хj) не имеют меток, то это означает невозможность приращения потока. Так достигают максимального значения потока от вершин-истоков хs и хt по дугам к вершинам - стокам хi и хj.

Алгоритм Форда-Фалкерсона.

шаг 1: присвоить всем вершинам графа индексы 0,1,2,...k; где 0-индекс вершины-истока графа, k -индекс вершины-стока графа;

шаг 2: присвоить начальной вершине метку “0”;

шаг 3: все непомеченные вершины хi, в которые идут ненасыщенные дуги из помеченной вершины хs, пометить индексом “+s”, что свидетельствует о возможности увеличения потока из вершины хs по дуге (хs, хi);

шаг 4: все непомеченные вершины хi, из которых идут дуги (насыщенные или ненасыщенные) в помеченную вершину хj, пометить индексом “-j”, что свидетельствует о возможности уменьшения потока в вершину хj по дуге (хi, хj);

шаг 5: если в результате этих операций окажется помеченной вершина-сток xk, то между начальной и конечной вершинами сети найдется маршрут, все вершины которого различны и с точностью до знака помечены индексами предыдущих вершин, формирующих переход, по которому можно увеличить поток, и перейти к шагу 6, иначе конец.

шаг 6: увеличить поток в маршруте, сформированном на шаге 5, на единицу и перейти к шагу 3.

Пример: На рис. 34 дан граф. Каждой дуге графа (хi, хj) приписаны величина потока и пропускная способность (jij,cij).  

Все расчеты по алгоритму сведены в две таблицы. В табл. а) на каждом шаге итерации для каждой вершины графа указаны возможные метки, а в табл. b) даны приращения потока по дугам (хij). Символом “      “ в табл. b) показаны насыщенные дуги графа. В результате выполнения первого шага итерации возможны маршруты: n0k={(хk, х1, х0); (хk, х2, х0); (хk, х2, х3, х0); (хk, х2, х3, х1, х0); (хk, х3, х0); (хk, х3, х1, х0)}, из множества которых был выбран маршрут m = (хk, х3, х0).

                                                                                                    табл. а)