Cтраница 2
Поскольку, таким образом, приведенная сеть может содержать по нескольку дуг одинаковой пропускной способности, равной пропускной способности одной дуги исходной сети, в данном случае можно говорить о приведении сети к последовательно-параллельной конфигурации при помощи размножения дуг. К последовательно-параллельной сети принципиально возможно привести любую исходную двухполюсную сеть. Пусть имеется произвольная двухполюсная сеть. Wt - множество вершин, определяющее i-тый разрез. [16]
Пусть G - подграф сети Г ( а, Ь), содержащий хотя бы одно ребро. Тогда вершина подграфа G называется граничной, если она либо является полюсом, либо инцидентна некоторому ребру сети, не принадлежащему подграфу G. Подграф сети называется отростком, если он обладает единственной граничной вершиной. Подсетью двухполюсной сети называется ее подграф, имеющий ровно две граничные вершины. Эти вершины называются полюсами подсети. Сеть Г ( а, b, G) называется связной, если ее граф G является связным. Тривиальной называется двухполюсная связная сеть, имеющая одно ребро. Связная сеть называется сильно связной, если через каждое ребро проходит цепь. [17]
Сечение двухполюсной сети есть совокупность ребер, при удалении которых сеть распадается на две или большее число несвязанных частей с двумя полюсами в разных частях. Таким образом, каждый путь от одного полюса к другому в исходной сети проходит хотя бы через одно ребро сечения. Под простым сечением будем подразумевать такое сечение, что если удалить любое его ребро, то оно перестанет быть сечением. Так ( d, е, f) и ( Ь, с, е, g, h) являются простыми сечениями, в то время как ( d, g, h, i) не является таковым. Если в связной двухполюсной сети удаляется простое сечение, то сеть распадается ровно на две части: левую часть, содержащую левый полюс, и правую часть, содержащую правый полюс. Каждому простому сечению припишем значение, равное сумме пропускных способностей ребер этого сечения, причем пропускная способность ориентированного ребра учитывается только тогда, когда оно направлено из левой части сети в правую часть. [18]