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

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

3. Понятия транспортной сети

Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c(ei), называемое пропускной способностью дуги, и существует:

- ровно одна вершина Vo = S, в которую не заходит ни одна дуга, называемая источником или началом сети;

- ровно одна вершина Vn=t, из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.

Потоком сети называется неотрицательная функция f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.)

Дуга e=(Vi,Vj) называется насыщенной потоком f, если f(Vi, Vj) = c(Vi, Vj)=c(e) (Поток называется полным, если содержит насыщенную дугу f(e)=c(e).)

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