назад

3.7 Двухполюсные сети. Потоки в сетях.

1. Граф, некоторые вершины которого выделены, называется сетью. Выделенные вершины называются полюсами сети. Например, дерево с корнем можно рассматривать как однополюсную сеть. Вершины, отличные от полюсов, называются внутренними вершинами сети. Ребро, инцидентное хотя бы одному полюсу, называется полюсным ребром; остальные ребра называются внутренними.

(k, l)- полюсником называется сеть с (k + l) полюсами, разбитыми на два класса: k входных и l выходных полюсов. (1, 1)-полюсник называется также двухполюсной сетью. В этом параграфе мы будем рассматривать, главным образом, двухполюсные сети без петель и без изолированных внутренних вершин (кратные ребра допускаются). Они будут называться просто сетями. Будем также называть цепью (без указания концов) элементарную цепь между полюсами сети - в других случаях будем обязательно указывать концы цепи или называть ее цепочкой. Обозначим входной и выходной полюсы сети S символами s и βs. Полюсные ребра образуют входную и выходную звезды Zas и ZBs - пересечение которых состоит из сквозных ребер (оно может быть пустым), инцидентных обоим полюсам.

Пусть А и В - две цепи сети S, не имеющие общих внутренних вершин, и β- внутренние вершины этих цепей, С - элементарная цепочка [, β], не пересекающаяся с А и В нигде, кроме своих концов (рисунок 11). Тогда существуют две цепи, проходящие через цепочку С в разных направлениях: sA1C β >B2βs и sB1βCA2βs. Подграф, образованный парой таких цепей А и В и связывающей их цепочкой С, называется мостиком.


Рисунок 11

2. Рассмотрим две операции над сетями. Пусть S1 - сеть с полюсами 1, и β1, S2 - сеть с полюсами 1, и β1, причем S, и S2 не имеют общих элементов. Сеть S1 ∙ S2 с полюсами 1, и β2, полученная склеиванием вершин β1 и 2, называется последовательным соединением сетей S1 и S2 (рисунок 12а); сеть S1 S2 с полюсами 1 и β1 полученная склеиванием полюсов 1 с 2 и β1,с β2, параллельным соединением сетей S1 и S2 (рисунок 126). Аналогично определяют последовательное и параллельное соединения большего числа сетей S1.S2....Sn и S1S2...Sn.


aб
Рисунок 12

Сеть, полученная из однореберных сетей в результате конечного числа параллельных и последовательных соединений, называется параллельно-последовательной сетью. Другими словами, класс параллельно-последовательных сетей (сокращенно П-сетей) определяется индуктивно:

(1) однореберная сеть есть П-сеть

(2) если S1 и S2 - П-сети, то S1 ∙ S2 и S1 S2 - тоже П-сети.

Характеристическое свойство П-сетей: они не содержат мостиков.

3. Добавим к сети S дополнительное, источниковое ребро, связывающее полюсы (иногда, например, в случае ориентированных сетей бывает удобным ориентировать это ребро от выхода к входу сети). Полученную расширенную сеть обозначим через . Заметим, что добавление источникового ребра к любой цепи А превращает ее в элементарный цикл .

Нетрудно показать, что в произвольной сети сумма по модулю 2 нечетного числа цепей Ai содержит цепь. В самом деле, сложим по модулю 2 циклы i , соответствующие данным цепям Аi. В результате получим четный граф i . Источниковое ребро входит в эту сумму, таккак оно участвует в сложении нечетное число раз. Очевидно, что оно является циклическим ребром в i; (напомним, что в четном графе, все ребра циклические). Содержащий его цикл после удаления самого источникового ребра есть искомая цепь.

4. Пусть S - произвольная частично ориентированная сеть, каждому ребру е которой приписано неотрицательное число с(е) - пропускная способность. Потоком в сети S называется пара (f, ), где - некоторая ориентация всех неориентированных ребер сети, a f(e) - заданная на множестве всех ребер функция с неотрицательными значениями, не превосходящая пропускных способностей, и такая, что в каждой внутренней вершине выполнен закон Кирхгофа, согласно которому сумма значений потока по ребрам, входящим в вершину, равна сумме значений потока по ребрам, исходящим из вершины. Другими словами, для f(e) выполнены условия:

(1) 0 ≤ f(e) ≤ с(е) для всех ребер сети;

(2) R( ) = 0 для всех внутренних вершин , где

а Г() (соответственно Г'()) - множество всех ребер, исходящих из (соответственно входящих в ) при ориентации .

Поскольку сумма значений R() по всем вершинам сети, включая полюсы, равна 0 (каждое ребро является исходящим для одной вершины и входящим для другой), то R(s) = -R(βS). Значение R = R(s) называется величиной потока. Между прочим, сходные рассуждения показывают, что если сеть допускает поток ненулевой величины, то полюсы сети находятся в одной компоненте связности. Если сеть изображает какую-либо проводящую систему (сеть дорог, трубопровод и т.п.), то R определяет величину потока, входящего в одном полюсе и выходящего из другого, т.е. проходящего через сеть. Если на ориентированном от βs к s источниковом ребре положить f = R (допуская, что для этого ребра f может быть меньше 0), то закон Кирхгофа будет выполняться для всех вершин сети, а R будет определять величину циркуляции через сеть.

5. Поставим задачу определить максимальную величину потока Rmax через сеть S при заданных значениях пропускных способностей. Ответ может быть получен в терминах сечений сети.

Сечением в сети называется множество ребер, при удалении которого сеть становится несвязной, причем полюсы попадают в разные компоненты связности. Ясно, что каждая цепь (а тем более каждый путь из s в βs) проходит хотя бы через одно ребро сечения. В сети на рисунке 13 примерами сечений являются {d, е, f}, {b, с, е, g, h}, {d, g, h, i}. Сечение будем называть простым, если при удалении любого его ребра оно перестает быть сечением. Так, {d, е, f} и {Ь, с, е, g, h} являются простыми сечениями, в то время как {d, g, h, i} не является таковым: можно удалить ребро h или ребро i. Очевидно, что для каждого ребра простого сечения можно указать цепь, которая проходит через это ребро, но не проходит через другие ребра данного сечения: иначе это ребро было бы излишним.


Рисунок 13

Если в связной сети удаляется простое сечение, то сети распадается ровно на две части левую часть, содержащую s, и правую часть, содержащую βs Каждое ребро простого сечении связывает вершины из разных частей. Будем называть ребро сечения прямым, если оно в сету не ориентировано или ориентировано слева направо, и обратным -в противном случае. Будет ли ориентированное ребро прямым и обратным, вообще говоря, зависит от выбора сечения. Так, в примере на рисунке 13 ребро е в сечениях {d, е, f} и {Ь, с, е, g, h} - обратное, а сечении {а, с, е, g, i} - прямое.

Каждому простому сечению W припишем пропускную способность c(W), равную сумме пропускных способностей всех его прямых ребер. В примере на рисунке 13 сечение {d, е, f} имеет пропускную способность) 5 + 1 = 6, а сечение {Ь, с, е, g, h} - пропускную способность 3 + 2 + 3 + 2 = 10. Если сеть несвязна и ее полюсы находятся в разных компонентах связности, то естественно считать (единственным) простым сечением пустое множество, а его пропускную способность нулевой.

Теорема Форда-Фалкерсона о максимальном потоке: максимальная величина потока Rmax через сеть S равна минимально из пропускных способностей cmin ее простых сечений.

Неравенство Rmax ≤ cmin можно считать достаточно очевидным из физических соображений, и в его справедливости нетрудно убедиться, просуммировав величину R() по всем вершинам левой компоненты произвольного сечения W. Эта сумма, с одной стороны, равна R(s), а с другой стороны, она равна алгебраической сумме величин потоков, идущих через сечение слева направо (потоки по ребрам, идущим из левой компоненты в правую суммируются со знаком плюс, а по ребрам, идущим в обратном направлении, - со знаком минус). Поскольку f(e) с(е), отсюда следует, что R < c(W). Ясно также, что равенство R = c(W) может достигаться только, если все прямые ребра сечения W ориентированы слева направо (при ориентации ) и для них f(e) = с(е), а для всех обратных ребер f(e) = 0

Несколько сложнее доказывается, что в сети S можно создать поток величины, равной cmin.

Разработан ряд конкретных алгоритмов построения максимального потока, основанных на этой теореме.

Теорема Форда-Фалкерсона допускает обобщение на случай, когда пропускные способности приписаны не только ребрам, но и внутренним вершинам сети, и поток считается допустимым, если для любой внутренней вершины величина (так же как и величина ) не превосходит пропускной способности вершины .

Теорема распространяется и на (k, l) - полюсную сеть. В обоих случаях величина максимального потока от входов к выходам сети равна и минимальной пропускной способности множества элементов сети, блокирующего все цепи.

6. Наряду с определением максимальных потоков в тех или иных проводящих системах теорема Форда-Фалкерсона позволяет решать и некоторые чисто комбинаторные проблемы. Одна из них носит название задачи о назначениях. Пусть имеется N претендентов {} на N вакантных должностей {β}. Возможно ли назначение всех N кандидатов, если каждый из них способен занять одну из некоторого подходящего ему подмножества Вi этих должностей? Очевидным является следующее необходимое условие такой возможности: для любой группы k ≤ N претендентов объединение соответствующих им множеств Вi должно содержать не меньше k должностей - иначе им не хвнатит мест (вспомните комбинаторный принцип Дирихле).

Ситуация может быть представлена двудольным графом, где V1={ai}, V2 ={bj} и (ai, bj) - дуга графа, если кандидат ai, способен занять должность bj. Если ввести две дополнительные вершины - полюсы s и t, дополнительные дуги (s, аi) и (bj t), установить подходящим образом пропускные способности вершин и ребер, то с помощью теоремы Форда-Фалкерсона можно показать, что приведенное условие является также достаточным.

 

Вопросы для самоконтроля

  1. Дайте определение сети, полюса сети, внутренней вершины сети.
  2. Сформулируйте определение потока в сети, величина потока, сечение в сети.
  3. Сформулируйте теорему Форда-Фанкерсона.

Практические задания

Tест для самоконтроля