Главное меню

Вход на сайт

Кто на сайте?

Сейчас 154 гостей и ни одного зарегистрированного пользователя на сайте

На заданной сети (Рис. 1) найти максимальный поток из X4 в X1 и минимальный разрез.
Image

Решение

Необходимо заполнить таблицу:

  1  2  3  4  5  6  7 
 t   X1 2, +Х2 1, +Х6 2, +Х8 1, +Х6 1, +Х6 1,+Х8 
     X2 2, +Х3 1, +Х3   1, +Х6  
     X3 2, +Х4 1, +Х5   2, +Х5 1, +Х5 
 s   X4 ∞,+Х4,+Х4
,+Х4 ∞,+Х4 ∞,+Х4,+Х4
 ∞,+Х4
     X5 1, +Х4 1, +Х4 2, +Х7 2, +Х7 2, +Х7 1, +Х7 
     X6 2, Х3 1, +Х5 2, +Х7 1, +Х7 2, +Х5 1, Х5 
     X7 5, +Х4 5, +Х4 5, +Х4 3, +Х4 2, +Х4 1, +Х4 
     X8   2, +Х7   1, +Х6 
 V   2
   1
   2   1
   1
   1
 

Image

После первого шага увеличиваем потоки в дугах, которые сначала были везде = 0.
Далее продолжаем наращивать поток по цепям:
     Х4, Х3, Х2, Х1,        V1 = 2
     Х4, Х5, Х6, Х1,        V2 = 1
     Х4, Х7, Х8, Х1,        V3 = 2
     Х4, Х7, Х6, Х1,        V4 = 1
     Х4, Х7, Х5,              V5 = 1
     Х4, Х7, Х5, Х6, Х8,        V6 = 1
     Image, т.е. максимальный поток = 8.
На последнем, 7-ом шаге, на котором мы не достигли (не можем пометить) вершину t = Х1 находим все помеченные вершины:
     Xs = {X4}
     и непомеченные вершины
     Xt = {X1, X2, X3, X5, X6, X7, X8}.
Минимальный разрез – ребра, один конец которых лежит в Xs, а другой в Xt.
В нашем случае это:
     (Х4, Х3), V(Х4, Х3) = 2;
     (Х4, Х5), V(Х4, Х5) = 1;
     (Х4, Х7), V(Х4, Х7) = 5
      Image       
     Т.е. величина минимального разреза совпадает с максимальным потоком.

У Вас недостаточно прав для добавления комментариев.
Вам необходимо зарегистрироваться на сайте