Cтраница 2
Отметим заодно, что смешанный барьер - это, вообще говоря, не подграф, так как вхождение ребра в барьер не влечет за собой вхождения его концов. Пропускную способность с ( W) смешанного барьера V / определим как сумму пропускных способностей входящих в него вершин и ребер. [16]
А дуг орграфа D, которое обладает тем свойством, что любая простая орцепь из v в w проходит через дугу, принадлежащую А. Другими словами, разрезом в сети является не что иное, как шьразделяющее множество соответствующего орграфа D. Пропускной способностью разреза называется сумма пропускных способностей принадлежащих ему дуг. Мы будем рассматривать главным образом такие разрезы, которые обладают наименьшей возможной пропускной способностью, - так называемые минимальные разрезы. На рис. 29.1 примером минимального разреза является множество дуг ( v, z), ( x, z) ( у, z) и ( х, w); пропускная способность этого разреза равна шести. [17]
Сечение двухполюсной сети есть совокупность ребер, при удалении которых сеть распадается на две или большее число несвязанных частей с двумя полюсами в разных частях. Таким образом, каждый путь от одного полюса к другому в исходной сети проходит хотя бы через одно ребро сечения. Под простым сечением будем подразумевать такое сечение, что если удалить любое его ребро, то оно перестанет быть сечением. Так ( d, е, f) и ( Ь, с, е, g, h) являются простыми сечениями, в то время как ( d, g, h, i) не является таковым. Если в связной двухполюсной сети удаляется простое сечение, то сеть распадается ровно на две части: левую часть, содержащую левый полюс, и правую часть, содержащую правый полюс. Каждому простому сечению припишем значение, равное сумме пропускных способностей ребер этого сечения, причем пропускная способность ориентированного ребра учитывается только тогда, когда оно направлено из левой части сети в правую часть. [18]