Алгоритмы на графах и их приложения. Дорофеева В.И. - 16 стр.

UptoLike

ВУЗ: 

ОГУ | Орел

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

Рубрика: 

16
Попробуем перераспределить поток. Нам необходимо передать из вершины 4
поток, равный единице (зафиксирован в метке вершины). Задержим единицу
потока в вершине 2, то есть вернем единицу потока из вершины 4 в вершину 2.
Эту особенность зафиксируем в метке вершины 2 – [-4,1]. Тогда единицу пото-
ка из вершины 4 мы передадим по сети вместо той, которая задержана в верши-
не 2, а единицу потока из вершины 2 попытаемся передать по сети, используя
другие дуги. Итак, вершина 4 просмотрена, вершина 2 помечена, вершины 5 и 6
не помечены. Четвертый и пятый шаги очевидны. Передаем единицу потока из
вершины 2 в вершину 6 через вершину 5. Вершина-сток достигнута, найдена
цепочка 1→3→4→2→5→6, по которой можно передать поток равный единице.
При этом по прямым дугам поток увеличивается на единицу, а по обратным –
уменьшается. Суммарный поток в сети – 4 единицы.
4. Четвертая итерация (рисунок 9). Вершине 1 присваиваем метку [1,@].
Первый шаг. Помечаем вершину 3 – [1,4]. Второй шаг. Рассматриваем поме-
ченную, но не просмотренную вершину 3. Из нее выходит одна дуга – (3,4).
Вершину 4 пометить не можем – пропускная способность дуги исчерпана.
Помеченных вершин больше нет, и вершина сток не достигнута. Увели-
чивающую поток цепочку построить не можем. Найден максимальный поток в
сети, равный 4. Можно заканчивать работу.
1
2
3
5
6
4
[1,@]
[1,4]
2(2)
1(5)
2(6)
2(2)
1(3)
0(4)
1(7)
3(3)
Рисунок 9
Попробуем перераспределить поток. Нам необходимо передать из вершины 4
поток, равный единице (зафиксирован в метке вершины). Задержим единицу
потока в вершине 2, то есть вернем единицу потока из вершины 4 в вершину 2.
Эту особенность зафиксируем в метке вершины 2 – [-4,1]. Тогда единицу пото-
ка из вершины 4 мы передадим по сети вместо той, которая задержана в верши-
не 2, а единицу потока из вершины 2 попытаемся передать по сети, используя
другие дуги. Итак, вершина 4 просмотрена, вершина 2 помечена, вершины 5 и 6
не помечены. Четвертый и пятый шаги очевидны. Передаем единицу потока из
вершины 2 в вершину 6 через вершину 5. Вершина-сток достигнута, найдена
цепочка 1→3→4→2→5→6, по которой можно передать поток равный единице.
При этом по прямым дугам поток увеличивается на единицу, а по обратным –
уменьшается. Суммарный поток в сети – 4 единицы.


     4. Четвертая итерация (рисунок 9). Вершине 1 присваиваем метку [1,@].
Первый шаг. Помечаем вершину 3 – [1,4]. Второй шаг. Рассматриваем поме-
ченную, но не просмотренную вершину 3. Из нее выходит одна дуга – (3,4).
Вершину 4 пометить не можем – пропускная способность дуги исчерпана.

                                  1(5)
                        2                           5

                 2(2)           1(3)
                                             0(4)       1(7)
     [1,@]
             1                                                        6


                 2(6)                                          3(3)
                        [1,4]
                                  2(2)
                        3                           4



                                 Рисунок 9


     Помеченных вершин больше нет, и вершина сток не достигнута. Увели-
чивающую поток цепочку построить не можем. Найден максимальный поток в
сети, равный 4. Можно заканчивать работу.
                                       16

Страницы