Алгоритм построения максимального потока в транспортной сети

Цепью, соединяющей истокA₀со стокомA_n, (или просто цепью) в транспортной сети называется последовательность дуг A₀A₁, …, A_n‑1 A_n, в которой вершина A_i является началом i-ой дуги, а вершина A_i+1 – её концом (или, наоборот, A_i является концом i-ой дуги, а вершина A_i+1 – её началом).

Например, в следующей сети с заданным в скобках потоком

цепями являются последовательности AB, BC, CD и AC, CB, BD, причём в первой цепи направление дуги BC совпадает с направлением потока, а во второй цепи направление дуги CB противоположно направлению потока.

Определение. Дуга цепи называется допустимой дугой, если:

1) направление дуги совпадает с направлением потока и поток по этой дуге меньше её пропускной способности;

2) направление дуги противоположно направлению потока и поток по этой дуге больше нуля.

Цепь, соединяющая исток сети со стоком, называется увеличивающей, если все её дуги являются допустимыми.

Дата добавления: 2015-07-26; просмотров: 273; Нарушение авторских прав

Мы поможем в написании ваших работ!