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

UptoLike

ВУЗ: 

ОГУ | Орел

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

Рубрика: 

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

                                              0(5)
                                    2                            5

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


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



                               Рисунок 7
     3. Третья итерация (рисунок 8). Вершине 1 присваиваем метку [1,@].


                           [-4,1]                                    [2,1]
                                              1(5)
                                    2                            5


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



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



                                             Рисунок 8


Первый шаг. Результат метка [1,5] у вершины 3. Второй шаг – метка [3,1] у
вершины 4. Пропускная способность дуги (4,6) израсходована полностью. Од-
нако есть обратная дуга (2,4), по которой передается поток, не равный нулю.

                                                     15

Страницы