20. Понятие максимального потока в сети. Задача поиска максимального потока в сети. Практические задачи, сводимые к задаче, поиска максимального потока. Алгоритм поиска максимального потока

Алгоритм поиска максимального потока построен на поиске увеличивающих цепей для какого-либо начального потока.

Цепь является увеличивающей, если в она состоит из дуг, позволяющих увеличить достигнутый в ней  результирующий поток. Дуги, позволяющие увеличить результирующий поток в цепи называются допустимыми.  Дуга является допустимой, если поток в ней совпадает с направлением цепи и имеет значение меньшее чем пропускная способность. Такие допустимые дуги называются согласованными. Величина на которую согласованная дуга позволяет повысить поток по цепи рассчитывается как разность между ее пропускной способностью и достигнутой величиной потока.

Кроме того, допустимой является дуга ,в которой поток совпадает с направлением цепи. Такие допустимые дуги называются несогласованными. Величиной, на которую позволяет увеличить поток в цепи несогласованная дуга является достигнутое  в ней значение потока.

Результирующий поток по цепи определяется потоком в самой «узкой» дуге, то есть дуге с минимальным потоком, следовательно величина на которую можно увеличит результирующий поток определяется минимальным значением увеличения, определенным для всех дуг.

Ссылка на основную публикацию
Adblock detector