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

UptoLike

ВУЗ: 

ОГУ | Орел

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

Рубрика: 

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

Страницы