Дискретная математика: графы и автоматы. Альпин Ю.А - 52 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

52 Глава 3. Задача о максимальном потоке в сети
Процесс помечивания заканчивается в двух случаях:
1) Ни одну вершину больше нельзя пометить, но сток не помечен.
Тогда алгоритм останавливается. 2) Сток помечен. Тогда произво-
дится изменение потока.
Изменение потока. Пусть сток получил метку (m
+
, δ). Тогда при-
бавляем δ к f
mt
и переходим в вершину m. Общий шаг: если мы нахо-
димся в вершине j с меткой (i
+
, x), то прибавляем δ к f
ij
и переходим
в i. А если метка j равна (i
−
, x), то вычитаем δ из f
ij
и переходим
в i. Заметим, что правило формирования меток таково, что после
прибавления δ новое значение потока не превышает пропускной спо-
собности дуги, а при вычитании δ не получается отрицательной вели-
чины. Продолжаем изменение потока, пока не достигнем источника.
Почему это непременно случится? Представим себе, что мы нумеруем
вершины по мере их помечивания. Тогда вершины, помеченные из v,
получают номер, б´ольший, чем номер вершины v. При изменении по-
тока переход совершается наоборот, от вершины с б´ольшим номером
к вершине с меньшим номером. Пока не достигнем вершины номер
один — источника.
Следует еще убедиться в том, что при изменении потока не нару-
шается условие 2) в определении потока. При прохождении вершины
j возможны четыре случая:
i
f
ij
+δ
−→ j
f
jk
+δ
−→ k
i
f
ij
+δ
−→ j
f
kj
−δ
←− k
i
f
ji
−δ
←− j
f
kj
−δ
←− k
i
f
ji
−δ
←− j
f
jk
+δ
−→ k
Легко проверить, что условие 2) во всех случаях
по-прежнему выполняется.
Величина измененного потока на δ > 1 больше, чем у исходного
потока. Теперь снова переходим к помечиванию. Схема алгоритма
такова:
пометился
не
сток
если
?
КОНЕЦ
ПОМ
если сток пометился
-
¾
ИЗМ
Поскольку поток увеличивается не меньше, чем на единицу, а ве-
личина потока не может превышать пропускной способности любого
разреза, то алгоритм останавливается после конечного числа шагов.
52                                      Глава 3. Задача о максимальном потоке в сети


    Процесс помечивания заканчивается в двух случаях:
    1) Ни одну вершину больше нельзя пометить, но сток не помечен.
Тогда алгоритм останавливается. 2) Сток помечен. Тогда произво-
дится изменение потока.
    Изменение потока. Пусть сток получил метку (m+ , δ). Тогда при-
бавляем δ к fmt и переходим в вершину m. Общий шаг: если мы нахо-
димся в вершине j с меткой (i+ , x), то прибавляем δ к fij и переходим
в i. А если метка j равна (i− , x), то вычитаем δ из fij и переходим
в i. Заметим, что правило формирования меток таково, что после
прибавления δ новое значение потока не превышает пропускной спо-
собности дуги, а при вычитании δ не получается отрицательной вели-
чины. Продолжаем изменение потока, пока не достигнем источника.
Почему это непременно случится? Представим себе, что мы нумеруем
вершины по мере их помечивания. Тогда вершины, помеченные из v,
получают номер, бо́льший, чем номер вершины v. При изменении по-
тока переход совершается наоборот, от вершины с бо́льшим номером
к вершине с меньшим номером. Пока не достигнем вершины номер
один — источника.
    Следует еще убедиться в том, что при изменении потока не нару-
шается условие 2) в определении потока. При прохождении вершины
j возможны четыре случая:
      fij +δ   fjk +δ
     i −→ j −→ k
      fij +δ   fkj −δ
     i −→ j ←− k
      fji −δ   fkj −δ         Легко проверить, что условие 2) во всех случаях
     i ←− j ←− k              по-прежнему выполняется.
      fji −δ   fjk +δ
     i ←− j −→ k
   Величина измененного потока на δ > 1 больше, чем у исходного
потока. Теперь снова переходим к помечиванию. Схема алгоритма
такова:
                                        если сток пометился
                                                          -
                                ПОМ ¾                         ИЗМ
                             если
                             сток
                               не
                        пометился
                                    ?
                                КОНЕЦ


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

Страницы