Контрольная работа по "Информатике"

 

 

 

 

2. Задача о максимальном потоке

Найти максимальный поток в сети.

 

         0  

              

 

Итерация 1.

Положим остаточные пропускные способности (cij, cji) всех ребер равными первоначальным пропускным способностям (Сij , Cji).

Шаг 1. Назначаем а1=∞ и помечаем узел 1 меткой [∞, -]. Полагаем i=1.

Шаг 2. S1= [2,3,4] (

Шаг 3. k=4, поскольку с14=max{c12,c13,c14}=max{10,15,25}=25. Назначаем а4 =с14 =25 и помечаем узел 4 меткой [25,1]. Полагаем, что i=4 и  возвращаемся к шагу 2.

Шаг 2. S2= [5] ( с43=0, поэтому узел 3 не включается в S2).

Шаг 3. k=5, поскольку с45=max{10} =10. Помечаем узел 5 меткой [10,4]. Получен сквозной путь. Переходим к шагу 5. 

Шаг 5. Сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1:

(5) → [10,4]→ (4) → [25,1]→ (1). Таким образом, N1 = {1,4,5} и f1=min{a1, a4,a5} = {∞; 25;10} =10.

 

 

 [∞, -]                                                         [25,1]

 

         0  

              

                                                                   [10,4]

 

Вычисляем остаточные пропускные способности  вдоль пути N1:

(с14, с41) = (25-10; 0+10) = (15, 10);

(с45, с54) = (10-10; 0+10) = (0,10).

 

Итерация 2.

Шаг 1. Назначаем а1=∞ и помечаем узел 1 меткой [∞, -]. Полагаем i=1.

Шаг 2. S1= [2,3,4] (

Шаг 3. k=3, назначаем а3=с13=max{c12,c13,c14}=max{10,15,15}=15. Помечаем узел 3 меткой [15,1]. Полагаем, что i=3 и  возвращаемся к шагу 2.

Шаг 2. S2= [4,5] ( с32=0, поэтому узел 2 не включается в S2).

Шаг 3. k=5, поскольку а5= с35=max{c34,c35}= max {6,25} =25. Помечаем узел 5 меткой [25,3]. Получен сквозной путь. Переходим к шагу 5. 

Шаг 5. Сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1:

(5) → [25,3]→ (3) → [15,1]→ (1). Таким образом, N2 = {1,3,5} и f2=min{a1, a3,a5} = {∞; 15;25} =15.

Вычисляем остаточные пропускные способности  вдоль пути N2:

(с13, с31) = (15-15; 0+15) = (0,15);

(с35, с53) = (25-15; 0+15) = (10,15).

[∞, -]                                                        

                                                [15,1]

        

              

                                                                   [25,3]

 

 

Итерация 3.

Шаг 1. Назначаем а1=∞ и помечаем узел 1 меткой [∞, -]. Полагаем i=1.

Шаг 2. S1= [2,4] (( с13=0, поэтому узел 3 не включается в S1).

Шаг 3. k=4, поскольку а4=с14=max{c12,c14}=max{10,15}=15. Помечаем узел 4 меткой [15,1]. Полагаем, что i=4 и  возвращаемся к шагу 2.

Шаг 2. S2= ( поскольку с43= с45=0). Переходим к шагу 4.

Шаг 4. Метка [15,1] узла 4 показывает номер предшествующего узла r=1. На этой итерации узел 4 в дальнейшем во внимание не принимается, его метку вычеркиваем. Полагаем i=1и возвращаемся к шагу 2.

Шаг 2. S3= [2]( с13=0, поэтому узел 3 не включается в S3, а узел 4 удален из возможных сквозных путей).

Шаг 3. k=2, а2=с12=10. Помечаем узел 2 меткой [10,1]. Полагаем i=2 и возвращаемся к шагу 2.

Шаг 2. S4= [3,5](

Шаг 3. k=5, поскольку а5=с25=max{c23,c25}=max{15,28}=28. Помечаем узел 5 меткой [28,2]. Получен сквозной путь. Переходим к шагу 5. 

 

Шаг 5. Сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1:

(5) → [28,2]→ (2) → [10,1]→ (1). Таким образом, N3 = {1,2,5} и f3=min{a1, a2,a5} = {∞; 10; 28} =10.

Вычисляем остаточные пропускные способности  вдоль пути N3:

(с12, с21) = (10-10; 0+10) = (0;10);

(с25, с52) = (28-10; 0+10) = (18;10).

[∞, -]                                                          [15, 1]                                                     

                                                [15,1]

        

              

 [10,1]                                                          [28,2]

 

 

Итерация 4.

Шаг 1. Назначаем а1=∞ и помечаем узел 1 меткой [∞, -]. Полагаем i=1.

Шаг 2. S1= [4] ( с12= с13=0, поэтому узлы 2 и 3 не включаются в S1).

Шаг 3. k=4, поскольку а4=с14=15. Помечаем узел 4 меткой [15,1]. Полагаем, что i=4 и  возвращаемся к шагу 2.

Шаг 2. S2= ( поскольку с43= с45=0). Переходим к шагу 4.

Шаг 4. Метка [15,1] узла 4 показывает номер предшествующего узла r=1. На этой итерации узел 4 в дальнейшем во внимание не принимается, его метку вычеркиваем. Полагаем i=1и возвращаемся к шагу 2.

Шаг 2. S3= (с12= с13=0, поэтому узлы 2 и 3 не включаются в S3, а узел 4 удален из возможных сквозных путей). Сквозных путей нет. Переходим к шагу 6 для определения решения.

[∞, -]                                                          [15, 1]                                                     

                                               

        

              

 

Шаг 6. Максимальный объем потока в сети равен F = f1 + f2 + f3 = 10+15+10=35 единиц.

Значения потоков по различным ребрам вычисляются путем вычитания последних значений остаточных пропускных способностей из первоначальных значений пропускных способностей.

Результаты вычислений приведены в таблице:

Таблица 1 – Результаты 4 итерации

Ребро	(Сij , Cji) - (cij, cji)	Величина потока	Направление
(1,2)	(10,0) – (0,10) = (10,-10)	10	1→ 2
(1,3)	(15,0) – (0,15) = (15,-15)	15	1→ 3
(1,4)	(25,0)-(15,10) = (10,-10)	10	1→ 4
(2,5)	(28,0) –(18,10) = (10,-10)	10	2→ 5
(3,5)	(25,0) – (10,15) = (15,-15)	15	3→ 5
(4,5)	(10,0) – (0,10) = (10,-10)	10	4→ 5