Алгоритм построения максимального потока в транспортной сети
Цепью, соединяющей исток A0 со стоком An, (или просто цепью) в транспортной сети называется последовательность дуг A0A1, …, An‑1 An, в которой вершина Ai является началом i-ой дуги, а вершина Ai+1 – её концом (или, наоборот, Ai является концом i-ой дуги, а вершина Ai+1 – её началом). Например, в следующей сети с заданным в скобках потоком
цепями являются последовательности AB, BC, CD и AC, CB, BD, причём в первой цепи направление дуги BC совпадает с направлением потока, а во второй цепи направление дуги CB противоположно направлению потока. Определение. Дуга цепи называется допустимой дугой, если: 1) направление дуги совпадает с направлением потока и поток по этой дуге меньше её пропускной способности; 2) направление дуги противоположно направлению потока и поток по этой дуге больше нуля. Цепь, соединяющая исток сети со стоком, называется увеличивающей, если все её дуги являются допустимыми.
|
