Задача о максимальном потоке

Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.

Рассмотрим граф G=(X,U), называемый в дальнейшем сетью. Пусть каждой дуге (x_i, x_j) сопоставлено положительное число c_ij, называемое пропускной способностью дуги. В сети выделяют два специальных узла, один из них называют источником (обозначим его через s), другой – стоком (обозначим его через t). Множество неотрицательных чисел f_ij, определенных на дугах (x_i,x_j), называют потоками в дугах, если выполняются следующие условия:

Задача о максимальном потоке состоит в нахождении такого множества потоков по дугам, чтобы величина потокаv в сети была максимальной при условии отсутствия превышения пропускных способностей дуг.

Заносим данные (пропускные способности) в таблицу. В ячейки таблицы записываем пропускную способность звеньев из Р_i пункта в Р_j элементом (i, j), а (j, i) – пропускная способность звена в обратном направлении. Если элемент (i, j) > 0, а (j, i) = 0, то на месте элемента (j, i) следует записать 0. Выберем произвольно один из возможных путей. Определяем пропускную способность выбранного пути:

Вычисляем минимуму пропускных способностей Х₁⁰. Вычитаем Х₁ из ячеек со знаком "-" и прибавляем в ячейки со знаком "+".Строим новый путь.

Вычитая из элементов первой таблицы элементы последней, получаем итоговую таблицу со значениями (i, j), определяющими максимально возможный поток.