Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети

§1. Понятие орграфа

§2. Обходы в орграфах

§3. Бесконтурные графы

§4. Пути в сетях

§5. Потоки в сетях

Пусть N=(G,a) – сеть, имеющая один источник a и один сток b. Предположим, что сеть N представляет собой схему линий связи, где вершинам соответствуют узлы связи, дугам – линии связи с указанным направлением передачи информации. Если е – дуга сети N, то величина a(е) означает ограничение количества информации, передаваемой по дуге е за некоторый промежуток времени. Возникает следующий вопрос. Какое наибольшее количество информации можно передать из а в b и как это сделать? Ответу на поставленный вопрос и посвящен этот параграф.

Следуя приведенной выше интерпретации сети, условимся величину a(е) называть пропускной способностью дуги е.

Центральным понятием параграфа является понятие потока в сети.


Рис. 6.15

Рис. 6.16


Определение. Пусть N=(G,a) – сеть, а – источник и b – сток этой сети. Потоком через сеть N называется функция

j:Е®R+È{0},

удовлетворяющая двум условиям:

1) j(е)£a(е) для любой дуги еÎЕ,

2) в сети (G,j) у любой вершины, кроме источника и стока, полустепень исхода равна полустепени захода. Число j(е) называется значением потока через дугу е.

На рис. 6.16 приведен пример потока через сеть, изображенную на рис. 6.15. Значения функции j указаны в скобках.


Предложение. Пусть j - поток через сеть N=(G, a). Тогда сумма потоков через дуги, инцидентные источнику, равна сумме потоков через дуги, инцидентные стоку.


Доказательство. Пусть V={v1,v2,…,vn}, причем v1 – источник, v2 - сток. Рассмотрим сеть N’=(G,j). В сети N’ сумма полустепеней исхода всех вершин равна сумме полустепеней захода всех вершин


r(v1) + r(v2) + r(v3) +… + r(vn) = r+(v1) + r+(v2) + r+(v3) + … + r+(vn),


поскольку для любой дуги е число j(е) участвует ровно один раз, как в левой, так и в правой сумме. Так как j - поток, то r(vi) = r+(vi) для i=3,…,n. Это означает, что r(v1) + r(v2) = r+(v1) + r+(v2). Из последнего равенства получаем равенство r(v1) = r+(v2), потому что

r(v2) = 0 и r+(v1) = 0.


Предложение доказано.


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


Величину потока j будем обозначать через ½j½. Поток, приведенный на рис. 6.16, имеет величину 5. Этот поток является максимальным, поскольку его значение на дугах, инцидентных стоку, равно сумме пропускных способностей этих дуг. Сеть может иметь несколько максимальных потоков, как показывает пример, приведенный на рис. 6.17


Рис. 6.17

Рис. 6.18


При изучении максимальных потоков в сети используется понятие разреза.


Определение. Разрезом сети N, имеющей один источник и один сток, называется множество дуг S такое, что любой путь из источника в сток проходит через дугу из S.


Определение. Пропускной способностью разреза называется сумма пропускных способностей входящих в него дуг. Разрез называется минимальным, если он имеет наименьшую пропускную способность (среди всех разрезов данной сети). Пропускную способность разреза S будем обозначать через a(S).


Так, например, для сети на рис. 6.18 примерами разрезов будут множества S1={(a,y), (a,x), (a,z)}, S2={(a,z), (x,z), (y,z), (y,b)}, S3={(y,b), z,b)}. Эти разрезы имеют пропускные способности соответственно 7,6 и 6. Разрезы S2 и S3 являются минимальными. Мы видим, что минимальных разрезов может быть несколько.

Оказывается, что для любой сети величина максимального потока совпадает с пропускной способностью минимального разреза. Этот результат был получен американскими математиками Фордом и Фолкерсоном в 1955 году. Мы приведем его доказательство, однако прежде отметим ряд вспомогательных фактов.


Если j - поток через сеть N=(G,a), то через Gj будем обозначать суграф графа G, содержащий дуги, по которым проходит ненулевой поток (и только такие дуги).


Лемма 1. Для любого потока j через сеть N=(G,a) существует поток j через ту же сеть такой, что ½j½=½y½ и Gy - бесконтурный подграф графа Gj.

Доказательство. Предположим, что граф Gj содержит контур С, проходящий по дугам е12,…,еl. Среди чисел j (e1), j(e2), …, j (el) выберем наименьшее, пусть это будет число m. Рассмотрим функцию θ:E®NÈ{0}, определяемую следующим образом:



Легко проверить, что θ – поток через сеть N, ½j½= ½θ½ и Gθ – подграф графа Gj. Граф Gθ уже не содержит контура С. Повторяя эту процедуру необходимое число раз, в итоге получаем необходимый поток y.

Лемма доказана.


Лемма 2. Пусть j - ненулевой поток через сеть N с источником а и стоком b. Тогда существует простой (a,b) – путь, проходящий по дугам с ненулевым потоком.

Доказательство. В силу леммы 1 можно считать, что граф Gj = (V,Ej) не содержит контуров. Пусть Va – множество вершин графа Gj, достижимых из вершины а. Поскольку граф Gj не содержит контуров, то множество Va содержит хотя бы одну вершину х, которая является стоком в графе Gj. Ясно, что х¹а. Если х¹b, то в графе G существуют дуги с ненулевым потоком, заходящие в х, и не существует дуг с ненулевым потоком, выходящих из х. Это противоречит определению потока. Следовательно, bÎVa, т.е. в графе Gj вершина b достижима из а. Это означает, что в сети N существует простой (a,b) – путь, проходящий по дугам с ненулевым потоком.

Лемма доказана.


Лемма 3. Величина любого потока через сеть не превосходит пропускной способности любого разреза этой сети.


Доказательство. Пусть j - поток через сеть N=(G,a), S – разрез этой сети. Напомним, что величину потока мы обозначаем через ½j½ а пропускную способность разреза – через a(S).

Предположим вначале, что функция j принимает целочисленные значения. Исходя из сети N и потока j, построим орграф G’ с кратными дугами. Множество вершин графа G’ совпадает с множеством вершин исходного графа G. Если е – (x,y)–дуга графа G и j(е)>0, то в графе G’ изображаем j (е) дуг, исходящих из х и заходящих в y. Если же j(е) = 0 или в G нет дуги из х в y, то в G’ тоже нет дуги из х в y. На рис. 6.20 изображен граф G’, построенный для сети N и потока (в скобках), представленных на рис. 6.19.


Рис. 6.19

Рис. 6.20

Из леммы 2 следует, что в графе G’ найдется множество Р из ½j½ простых (a,b)-путей, никакие два из которых не содержат общей дуги. Обозначим через S’ множество дуг графа G’, которые получились из дуг разреза S. Ясно, что S’ - разрез графа G’ и что количество дуг в S’ меньше или равно a(S). Каждый из путей множества Р содержит хотя бы одну дугу из S’, причем два различных пути не могут содержать одну и ту же дугу из S’. Это означает, что число путей в Р не превосходит число дуг в S’, т.е. ½j½=½Р½£½S’½£ a(S).

Рассмотрим теперь случай, когда функция j принимает рациональные значения. Пусть m – наибольшее общее кратное всех знаменателей значений функции j. Тогда функция m·j будет потоком в сети (G; m·a). Ясно, что множество S будет разрезом и в новой сети с пропускной способностью, равной m·a(S). В предыдущем абзаце было доказано, что ½m·j½£ m·a(S). Отсюда следует неравенство ½j½£a(S).

Общий случай, т.е. когда допускаются любые значения пропускных способностей и потоков, сводится к рассмотренному выше с помощью следующего утверждения. Для любой сети N=(G,a) с потоком j и разрезом S и любого числа e >0 существует рациональный поток j0 через ту же сеть, такой что - e <½j½½j0½<e и ½j0½£ a(S).


Лемма доказана.


Для дальнейшего введем ряд обозначений. Пусть N=(G,a) – сеть, имеющая источник а и сток b, D – множество вершин сети, такое, что aÎD, bÏD. Тогда множество ребер


{(u,v) ÎE½uÎD, vÏD}


обозначим через SD. Легко проверяется, что множество SD является разрезом сети. Этот разрез будем называть D–разрезом. Если X и Y – непустые множества вершин сети, а j - поток через сеть, то


j (X,Y)=S{ j(u,v)½uÎX, vÎY}.


Например, для сети, изображенной на рис. 6.19, если D={a,x,y}, X={a,x}, Y={x,y,b}, то SD={(a,z), (x,z), (y,b)}, j (X,Y)= j (a,x)+ j (a,y)+ j (x,y)=1+2+0=3.


Лемма 4. Пусть N=(G,a) – сеть, имеющая источник a и сток b, j - поток через эту сеть, D – множество вершин сети, содержащее a и не содержащее b. Тогда

½j½=j(D,) - j(D, ).


Доказательство. По определению потока для x¹a и x¹b имеем равенство

j (x,V) - j (V,x)=0,

а по определению величины потока – равенство

j (a,V) - j (V,a)=½j½.

Из этих равенств следует, что


½j½= (j (x,V) - j (V,x)) = j (D,V) - j (V,D).


Далее, поскольку j(X1ÈX2,Y)=j(X1,Y)+j(X2,Y) для X1ÇX2=Æ и j (X,Y1ÈY2)= j(X,Y) + j(X,Y2) для Y1ÇY2=Æ, то j(D,V) - j(V,D) = j(D,DÈ) - j(DÈ,D)=j(D,D)+j(D, ) - j(D,D) - j(,D)=j(D, ) - j(,D).


Лемма доказана.


Теорема. В любой сети величина максимального потока равна пропускной способности минимального разреза.


Доказательство. Пусть j - максимальный поток в сети N=(G,a). В силу леммы 3 достаточно доказать существование разреза S такого, что a(S)=½j½.

Можно считать, что Gj - бесконтурный граф (см. лемму 1).

Дугу e назовем насыщенной, если j(e)=a(e). Обозначим буквой D множество вершин сети, содержащее сток a и все вершины u, для которых существует последовательность


a=x0, x1,…, xk-1, xk=u,


такая, что дуга (xi, xi+1) ненасыщенна или через дугу (xi+1, xi) проходит ненулевой поток. Например, для сети, изображенной на рис. 6.21. D={a,y,z}. Отметим, что zÎD, хотя дуги (y,z) в сети нет.

Докажем, что bÏD. Предположим, что это не так, т.е. bÎD. Тогда существует последовательность вершин


a=y0,y1,…,yl-1,yl=b                             (*)


указанного выше вида (т.е. либо дуга (yi,yi+1) ненасыщенна, либо через дугу (yi+1,yi) проходит ненулевой поток). Пусть e - положительное число, которое меньше разности a(e) - j(e) для любой ненасыщенной дуги e и меньше любого ненулевого потока через дуги сети.

Изменим значение потока j на дугах цепи следующим образом. Если дуга (yi,yi+1) ненасыщенна, то положим j'( yi+1,yi+1) = j(yi,yi+1)+e. Если же эта дуга насыщена, то пусть j'(yi+1,yi) = j(yi+1,yi)-e. Для остальных дуг e значение потока оставим прежним: j ′(e) = j (e).

Нетрудно убедиться, что j′ - поток через сеть N. Действительно, ограничение j′(e) £ a(e) выполняется для любой дуги e по построению j′. Если через вершину v не проходит цепь (*), то суммарный поток через v равен нулю, поскольку это справедливо для j. Пусть v=yi для некоторого iÎ{1,…,l-1}. Возможны четыре случая определяемые насыщенностью или ненасыщенностью дуг (yi-1,yi) и (yi,yi+1). (Нам будет удобно отсутствующую дугу считать насыщенной) Рассмотрим только один из них: дуга (yi-1,yi) ненасыщенна, а дуга (yi,yi+1) насыщена. Обозначим буквой А множество вершин, из которых выходят дуги, заходящие в yi, буквой B множество вершин сети, в которые заходят дуги, выходящие из yi. Тогда


j(x,yi) = j(yi,z),                               (**)

поскольку j - поток. При переходе от j к j′ слагаемые в правой части не изменятся, а в левой изменятся два слагаемых: j(yi-1,yi) заменятся на j(yi-1,yi) + e, а j(yi+1,yi) - на j(yi+1,yi) - e, но вся сумма останется прежней. Следовательно, равенство (**) сохранится и при переходе от j к j′. Мы доказали, что j′ - поток через сеть N. Но его величина равна ½j½+ e, что противоречит максимальности потока j. Таким образом, bÏD.

Если uÎD и существует дуга, заходящая в u из вершины v, с ненулевым потоком, то vÎD. Это означает, что j(,D)=0. Рассмотрим разрез SD. Тогда из леммы 4 следует, что ½j½=a(SD), поскольку a(SD)= j(D, ).

Теорема доказана.

Рис. 6.21

Поскольку на чертеже разрез сети построить проще, чем найти поток через сеть, то теорему Форда-Фолкерсона в случае простых сетей можно использовать для нахождения максимальных потоков в сети. Однако для более-менее сложной сети, даже если найдена величина максимального потока, сам поток построить трудно. Приведем поэтому алгоритм, решающий задачу построения максимального потока для сетей с целочисленными пропускными способностями. Отметим, что в процессе работы алгоритма могут возникать сети, в которых нет ни источника, ни стока.


Алгоритм нахождения максимального потока

Дана сеть (G,a), a – источник, b – сток сети, a:E®N.


Шаг 1. Если не существует пути из источника в сток, то положить j=0 и перейти к шагу 4, иначе выбрать непустое множество T непересекающихся по дугам путей из a в b. Если e1,e2,…,ek – путь из T, т.е. последовательность дуг, то положить j(e1)= j(e2)=…= j(ek)=min{a(e1),…,a(ek)}. Для дуг e, через которые не проходят пути из T, положить j(e)=0. В результате получаем ненулевой поток j через сеть (G,a).


Шаг 2. Исходя из сети (G,a) и потока j построить сеть (G′,a′) следующим образом. Граф G будет иметь те же вершины, что и граф G. Если e – дуга графа G и a(e) - j(e)¹0, то e – дуга графа G′ и a′(e)=a(e) - j(e). Если e – дуга графа G и j(e)¹0, то вводим дугу  обратной ориентации, нежели e, и полагаем a′( ) = j(e). В случае, когда возникают кратные дуги e1 и e2, то вводим вместо них одну дугу e и полагаем a′(e)=a′(e1) + a′(e2).


Шаг 3. Если в сети (G′,a′) не существует пути из a в b, то перейти к шагу 4, иначе в сети (G’,a’) построить ненулевой поток j’ так, как это предписано шагом 1. Для сети (G,a) положить j=j+j’ и перейти к шагу 2.


Шаг 4. Выдать j. Конец работы алгоритма.


На примере сети, изображенной на рис 6.22, проиллюстрируем работу алгоритма. В качестве множества T на первом шаге алгоритма выбрано множество из двух путей: a,v1,v4,b и a,v2,v5,b.


Рис. 6.22


Рис. 6.23

На рис. 6.23 представлена сеть (G′,a′) полученная после выполнения шага 2 из сети на рис. 6.22 с указанным (в скобках) потоком j′. В качестве множества T для построения потока j′ взято множество, состоящее из одного пути: a,v3,v5,v2,v6,b. Поток j+j′ для сети (G,a) изображен на рис. 6.24. Этим завершен один проход алгоритма. Обратим внимание на то, что для e=(v2,v5) (j+j)(e)=j(e)–j′()=1.


Рис. 6.24


Рис. 6.25

Сеть построенная на шаге 2 второго прохода алгоритма, уже не имеет (a,b) – путей (см.рис. 6.25). Следовательно, на рис. 6.24 изображен максимальный поток.

Задачи

Ответы указания и решения


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru