double arrow

Замечание. Если в графе G = (V, A, j) существуют два истока S/1 и S/2, тогда добавляем к множеству вершин графа фиктивную вершину S/ и дуги (S/

Если в графе G = (V, A, j) существуют два истока S/1 и S/2, тогда добавляем к множеству вершин графа фиктивную вершину S/ и дуги (S/, S/1) и (S/, S/2); полагаем:

, .

Аналогично для двух стоков S//1 и S//2. Для преобразованного графа применим алгоритм Форда-Фалкерсона отыскания максимального потока в сети.


С понятием потока связано понятие разреза сети. Под разрезом сети понимается множество дуг сети Р(А), обладающих следующим свойством: любой путь от истока к стоку пройдет ходя бы по одной дуге разреза. При удалении дуг разреза сеть становится несвязной, т.е. сеть как бы разрезается.

Величиной разреза С(Р) называется сумма пропускных способностей входящих в него дуг: . Естественно необходимо найти разрез минимальной величины.

В сети величина максимального потока равна величине минимального разреза, т.е.

. (4.11)


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: