Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200

• Название: Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
• Анкор: Дискретная Математика
• Дата: 15.09.2022
• Размер: 6.37 Mb.
• Имя файла: S_D_Shaporev_-_Diskretnaya_matematika_-_2004.pdf
• Тип: Учебное пособие; #679116
• страница: 21 из 26

. (3.24.1)
Пропускной способностью или величиной разреза


//
/
S
S

называется сумма пропускных способностей входящих в него дуг, то есть









//
/
,
//
/
,
S
x
S
x
j
i
j
i
x
x
c
S
S
c
(3.24.2)
I разрез На рисунке 3.67 изображена сеть, на которой око-
2
x 1 4
x ло каждого ребра указана его пропускная способ-
3 II разрез ность. Произведены два разреза I и II. При разре-
1
x 2 5 зе I вершины оказались разбиты на подмножества
7 7 4 5
x


2 1
/
, x
x
S

и


5 4
3
//
,
,
x
x
x
S

, а ребрами, образу-
3
x ющими разрез стали ребра

 
 

4 2
4 1
3 1
,
,
,
,
,
x
x
x
x
x
x
Рис. 3.67.
При разрезе II


4 3
2 1
/
,
,
,
x
x
x
x
S

, а
 
5
//
x
S

,

99 разрез образуют ребра

 

5 4
5 3
,
,
,
x
x
x
x
3.25. Теорема Форда

– Фалкерсона
Теорема 3.29. Для любой сети с одним источником и одним стоком величина
максимального потока в сети от источника к стоку равна пропускной способности
минимального разреза.
Доказательство. Алгоритм Форда – Фалкерсона построения максимального потока и минимального разреза основан на следующих обстоятельствах.
1.
Предположим, что в сети имеется некоторый поток и путь из s в t , состоящий из ненасыщенных дуг. Тогда очевидно, что поток в сети можно увеличить на величину

, равную минимальной из остаточных пропускных способностей дуг, входящих в этот путь.
Перебирая все возможные пути из s в t и проводя такую процедуру увеличения потока, пока это возможно, получим в результате полный поток, т. е. такой поток, для которого каждый путь из s в t содержит по крайней мере одну насыщенную дугу.
2.
Рассмотрим произвольный маршрут (неориентированный путь) из s в t . Дуги, образующие этот маршрут, естественным образом делятся на два типа: прямые
(ориентированные от s к t ) и обратные (ориентированные от t к s ). Пусть существует путь, в котором прямые дуги не насыщены, а потоки на обратных дугах положительны. Пусть
1

- минимальная из остаточных пропускных способностей прямых дуг, а
2

- минимальная из величин потоков обратных дуг. Тогда поток в сети можно увеличить на величину


2 1
,
min




, прибавляя

к потокам на прямых дугах и вычитая

из потоков на обратных дугах (см. рис. 3.68). Очевидно, что при этом условие баланса (условие сохранения потока)




 
 





j
пр
i
i
сл
j
x
S
x
x
S
x
j
i
j
i
x
x
x
x
,
,


для узлов, входящих в рассматриваемый маршрут, не нарушится. Ясно, что если множество обратных дуг не пусто, то при такой процедуре увели- чения потока в сети фактического перемещения объек- тов вдоль рассматриваемого маршрута не происходит,


i
x


так как оно в принципе невозможно. Однако эта проце-
Рис. 3.68.
дура уменьшает потоки на некоторых дугах, которые, возможно, были перед этим насыщенными, образуя таким образом новые пути из ненасыщенных дуг, вдоль которых и происходит фактическое перемещение потока величины

Ясно также, что первая процедура является частным случаем второй.
Пример 1. Пропускные способности дуг заданы следующей матрицей. Построить максимальный поток от s к t и указать минимальный разрез, отделяющий s от t .
8 15 7
8 15 14 11 13 12 4
3 2
1 4
3 2
1















































t
x
x
x
x
s
t
x
x
x
x
s
Этап 1. Путь
15 3
14 1
12
t
x
x
s








12 15
,
14
,
12
min



Увеличим по этому пути поток до 12 единиц, ребро


1
, x
s
становится насыщенным. Поставим величину потока на дугах


3 1
, x
x
и


t
x ,
3
Путь
 
15 12 3
13
t
x
s

 





3 12 15
,
13
min




Поток можно увеличить на три

Лестер Форд (???? - ????) – американский математик.

100 1
x 15 4
x единицы. Дуга


t
x ,
3
станет насыщенной.
11(14) Путь
 
8 2
8 4
7 3
13 3
t
x
x
x
s







 

s 12(12) 7(8) 7(7) Можно увеличить поток на семь единиц; ду-
t га


4 3
, x
x
станет насыщенной, потоки на ду-
11(13) 15(15) гах примут вид (см. рис. 3.69):
 
 
 
 
8 7
2 8
7 4
7 7
3 13 10
t
x
x
x
s










 

2
x
3
x Разрез Больше путей нет. Конец первого этапа.
8(8) Этап 2. Рассмотрим теперь маршруты,
Рис. 3.69.
содержащие противоположные дуги.
Маршрут
 
 
 
8 7
2 11 1
14 12 3
13 10
t
x
x
x
s






 


 

Поток можно увеличить на единицу на дуге
 
t
x ,
2
Тогда потоки по дугам этого маршрута станут такими
 
 
 
 
8 8
2 11 1
1 14 11 3
13 11
t
x
x
x
s




 


 


 

Дуга
 
t
x ,
2
стала насыщенной.
Больше маршрутов нет. Поток максимален. Делаем разрез вокруг t по насыщенным дугам и получаем его величину 15+8=23 единицы.
3.26. Поток минимальной стоимости
Рассмотрим задачу определения потока, заданной величины θ от s к t в сети


D
U
S
G
,
,
,


, в которой каждая дуга


j
i
x
x ,
характеризуется пропускной способностью




j
i
x
x
c
,
и неотрицательной стоимостью


D
x
x
d
j
i

,
пересылки единичного потока из
i
x в
j
x
вдоль дуги


j
i
x
x ,
Если max
θ


, где max

- величина максимального потока в сети G от s к t , то решения нет. Если же max
θ


, то может быть определено несколько различных потоков величины θ от s к t . Математическая модель задачи выглядит следующим образом.
Минимизировать

 






U
x
x
j
i
j
i
j
i
x
x
x
x
d
,
,
,

, (3.26.1) где


j
i
x
x ,

- поток по дуге


j
i
x
x ,
при ограничениях:
1)

 
 

U
x
x
x
x
c
x
x
j
i
j
i
j
i




,
,
,
0

;
2) для начальной вершины
 
 







S
x
S
x
i
i
i
i
s
x
x
s
S
s
θ
,
,


- уравнение истока;
3) для конечной вершины
 
 








S
x
S
x
i
i
i
i
t
x
x
t
S
t
θ
,
,


- уравнение стока;
4) для любой другой вершины











S
x
S
x
j
i
i
j
j
i
i
x
x
x
x
t
s
x
0
,
,
,


- условие сохранения потока.
Если

μ - кратчайший путь от s к t в сети


D
U
S
G
,
,

,
 

μ
min
c
- минимальная из пропускных способностей дуг, входящих в путь

μ , и если
 


μ
θ
min
c
, то задача имеет тривиальное решение – весь поток θ направляется вдоль пути

μ . Общее решение задачи о потоке минимальной стоимости строится следующим образом. Сначала находится кратчайший путь

μ от s к t и величина
 

μ
max

максимально возможного потока вдоль этого пути. Если окажется, что
 


μ
θ
max

, то задача решена. В противном случае сеть модифицируют специальным образом. Затем опять находят кратчайший путь от s к t и максимально возможный поток вдоль этого пути в модифицированной сети. Процедуры модификации сети и нахождения кратчайшего пути в ней повторяются до тех пор, пока либо

101 нужное количество θ не будет переправлено, либо возникнет сеть, в которой нет пути от s к
t , что означает отсутствие решения у исходной задачи.
Модификация сети допускается только определенного порядка. Пусть


D
U
S
G
,
,
,


- исходная сеть, S - множество вершин,
U
- множество ребер,

- множество весов
(пропускных способностей дуг), D - набор стоимостей пересылки единичного потока из
i
x в
j
x
вдоль дуги


j
i
x
x ,
Модифицированная относительно данного потока

сеть


D
U
S
G

,

,

,




строится следующим образом.
1)
S
S


, то есть число и набор вершин в модифицированной сети не меняется.
2)
V
U
U



, где
V
- некоторое множество фиктивных дуг. Таким образом, после модификации число дуг сети увеличивается.
3) Если




0
,
и
,


i
j
i
j
x
x
S
x
x

, то дуга


j
i
x
x ,
включается в множество
V
. При этом полагается

 
 



,
,

,
,
,

i
j
j
i
i
j
j
i
x
x
d
x
x
d
x
x
x
x
c




Этот пункт применяется только к дугам, по которым проходит поток

, относительно которого происходит модификация сети.
4) Для всех ненасыщенных дуг, где нет противоположного потока, в том числе и для ненасыщенных дуг с потоком, относительно которого происходит модификация сети, то есть для



 



0
,
и
,
,
,
,



i
j
j
i
j
i
j
i
x
x
x
x
c
x
x
S
x
x


полагают

 
 

,
,
,
,

j
i
j
i
j
i
x
x
x
x
c
x
x
c




 

j
i
j
i
x
x
d
x
x
d
,
,


5) Для всех насыщенных дуг



 



0
,
и
,
,
,
,



i
j
j
i
j
i
j
i
x
x
x
x
c
x
x
S
x
x


полагают




,

,
0
,




j
i
j
i
x
x
d
x
x
c
Это довольно сложный и «длительный» алгоритм. Нахождение кратчайшего пути как в исходной, так особенно в модифицированной сети может потребовать использования алгоритма Беллмана – Мура. Кроме того решение типичных учебных задач требует три – четыре итерации алгоритма.
Пример 1. Пусть матрицами

и D заданы пропускные способности дуг сети и стоимости транспортировки единичного потока вдоль всех дуг. Требуется: 1) построить максимальный поток от s к t и указать минимальный разрез, отделяющий s от t ;
2) построить поток величины





max
4 3
θ

, имеющий минимальную стоимость, здесь
 
... - целая часть числа.
Построим рисунок соответствующей сети (см. рис. 3.70). Первое число на дугах соответствует стоимости транспортировки единичного потока вдоль этой дуги; второе число
– пропускная способность дуги.
Найдем максимальный поток от вершины s к вершине t по алгоритму Форда –
Фалкерсона.
9 14 13 9
7 9
12 10 9
,
10 9
17 13 11 6
11 11 13 4
3 2
1 4
3 2
1 4
3 2
1 4
3 2
1





























































































t
x
x
x
x
s
t
x
x
x
x
s
D
t
x
x
x
x
s
t
x
x
x
x
s
Этап 1. Путь
17 2
11
t
x
s






11 17
,
11
min



. Увеличим по этому пути поток

102 1
x 9(6)
3
x до 11 единиц, ребро


2
, x
s
станет насыщен- ным. Второй возможный путь
9(13)
10 4
13 2
11 1
13
t
x
x
x
s








s 7(11) 9(14) t


10 10
,
13
,
11
,
13
min



. Поток по этому пу-
12(11) ти равен 10 единицам. Дуга
 
t
x ,
4
станет на-
10(11) 13(17) 9(10) сыщенной. Третий путь, по которому возмо-
2
x 9(13)
4
x жен ненулевой поток – это путь
Рис. 3.70.
6 2
1 1
3
t
x
x
s






Здесь


1 6
,
1
,
3
min



. По этому пути можно увеличить поток лишь на единицу, при этом дуга


2 1
, x
x
станет насыщенной. Больше путей нет.
Этап 2. Рассмотрим маршруты с противоположными ребрами. Маршрут
5 2
11 3
6 1
2
t
x
x
x
s








Поток можно увеличить на две единицы на дуге


1
, x
s
Эта дуга станет насыщенной. Тогда потоки по этому маршруту будут такими:
 
 
 
 
14 17 2
2 11 3
2 6
1 13 13
t
x
x
x
s

 


 





 


Больше маршрутов нет. Поток максимален. На
1
x
3
x рисунке 3.71 на дугах графа стоят две цифры:
6(2) первая – пропускная способность дуги, вторая -
I II поток по дуге (насыщенные дуги выделены). Те-
13(13) перь можно сделать несколько разрезов, напри-
s 11(-2) 9 t мер, отделяя исток и сток. И по первому I, и по
11(11) второму II разрезу поток одинаков
24
max


11(11) 17(14) 10(10 Построим теперь поток величины
2
x 13(10)
4
x
18 24 4
3 4
3
θ
max




 







единиц. По рассмот-
Рис. 3.71. ренному алгоритму для этого надо построить кратчайший путь от s к t на графе


D
U
S
G
,
,

. Этот граф изображен на рисунке 3.72, веса всех дуг в нем положительны, можно использовать алгоритм Дейкстры.