Граф и его элементы

курсовая работа

3.1 Понятие увеличивающая дуга, цепь, разрез

Рассмотрим данные понятия на примере:

Разрезом L сети S(N, U) называется множество насыщенных дуг, отделяющих источник s от стока t.

Пусть задана сеть S=(N, U) с множеством вершин N и множеством дуг U.

Определение: дуга u є U, соединяющая вершины i є N, j є N сети S, называется допустимой дугой, если она обладает одним из следующих свойств:

а) направление дуги совпадает с направлением потока, и значение потока по этой дуге меньше ее пропускной способности:

u=(i, j), (u)<c(u) (1)

б) направление дуги противоположного направлению потока, и величина потока отлична от нуля:

u=(j, i), (u)>0 (2)

Дуги, обладающие первым свойством, называют увеличивающими; дуги, обладающие вторым свойством, - уменьшающими.

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

Пример 1: построим увеличивающую цепь для сети S=(N, U), представленной на рисунке 10.

Рисунок 10 - увеличивающая цепь

Над каждой дугой указана ее пропускная способность, в скобках - поток по этой дуге.

Цепь (s, 1, 2, 4, t) является увеличивающей, так как все дуги - допустимые:

- дуга (s, 1) - увеличивающая, так как она проходит по направлению потока, и поток по ней меньше ее пропускной способности:

5 < 10;

- дуга (1,2) - также увеличивающая дуга: 12 < 15;

- дуга (2,4) - уменьшающая, так как она проходит против потока и поток по ней 3 > 0;

- дуга (4, t) - увеличивающая: 1 < 4.

Делись добром ;)