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

Рассмотрим сеть, имеющую только один источник s и только один сток t. Рассмотрим задачу о потоке из узла s в узел t, причем s и t могут быть связаны произвольно сложной промежуточной сетью. Задача о максималь­ном потоке состоит в определении количества, которое можно перевезти из s в t. Формализуем эти понятия.

Узел s множества N называется источником потока f, если f(s, N) > 0; узел t называется стоком потока f, если f(t, N)<0; узел х называется ней­тральным, если f(s, N)=0. Поток с одним источником s и стоком t называ­ется потоком от s к t. При всех f(x, N)=0;f(s, N)=f(N,t) (все, что «вытекает» из источника, попадает в сток). Мощностью потока f называется число f(s,N)=f(N,t). Поток наибольшей мощности носит название макси­мального потока. Сечением (или разрезом) сети G = [N, а] относительно s и t называется разбиение узлов N на такие два множества S и S ', что . Пропускной способностью сече­ния называется величина (сумма пропускных способностей дуг, начала которых находятся в S, а концы - в S '). Сечение с наименьшей пропускной способностью называется минимальным сечени­ем. Связь между сечениями и потоками устанавливается следующей леммой.

Лемма. Если f - поток в сети G=[N,A] от s к t и (S, S’) - сече­ние в сети G, то мощность потока f не превосходит

C(S, S'), т. е. (6)

Если в (6) имеет место равенство, то сразу можно сделать вывод о максимальном потоке f и минимальном сечении C(S, S').

Теорема (о максимальном потоке и минимальном сечении). Для любой сети величина максимального потока из s в t равна пропускной спо­собности минимального сечения, отделяющего s от t.

Алгоритм отыскания максимального потока в сети называется алго­ритмом Форда - Фалкерсона.

Поиск по сайту: