3.4. Транспортные сети

Определение. Транспортной сетью называется орграф D = (V, X) с множеством вершин V, для которого выполняются условия:

1) существует одна и только одна вершина v1, называемая источником, такая, что D-1(v1) = 0 (т.е. ни одна дуга не заходит в v1);

2) существует одна и только одна вершина vn, называемая стоком, такая, что D(vn) = 0 (т.е. из vn не исходит ни одной дуги);

3) каждой дуге x Î X поставлено в соответствие целое число c(x) 0, называемое пропускной способностью дуги.

Определение. Вершины в транспортной сети, отличные от источника и стока, называются промежуточными.