в стек первую строку матрицы

Продолжим исследование приведенной выше сети.

1. 
   Заносим в стек первую строку матрицы S. Находим первый нуль после обязательного нуля в первой позиции. Этот нуль указывает, что каналы 1 и 2 взаимно независимы (параллельны). Складываем логически строки, соответствующие каналам 1 и 2. Получаем новую строку s1 в вершине стека
   
   
   Она содержит нули правее позиции 2. Это говорит о том, что 1 и 2 не исчерпывают ПМВНК.
   
2. 
   Находим первый нуль правее позиции 2 — нуль в позиции 3. Складываем логически s2 = s1
   
   "3". Получаем новую строку в вершине стека и весь стек в виде
   
   
   Строка в вершине стека содержит нули только в тех позициях, которые соответствуют образующим ее каналам 1, 2, 3. Это означает, что мы нашли ПМВНК {1, 2, 3}, т.е. некоторый разрез сети. Минимальный поток, проходящий через него, составляет d1 + d2 + d3.
   
3. 
   Исключаем из стека строку s2 и в строке s1 испытываем следующий нуль правее позиции 2. Это нуль в позиции 4. Формируем новую вершину стека s3 = s1
   
   "4".
   
   
   Строка s3 содержит нули не только в позициях 1, 2, 4. Первый такой нуль правее позиции 4 — в позиции 7.
   Формируем новую вершину стека s4 = s3
   
   "7". Стек принимает вид
   
   
   Строка s4 содержит нули только в позициях, соответствующих каналам, "участвующим" в ее формировании. Значит, найдено еще одно ПМВНК {1, 2, 4, 7}. Оно определяет разрез сети с пропускной способностью d1 + d2 + d4 + d7.
   
4. 
   Исключаем s4 из стека. Следующий испытываемый нуль в строке s3 занимает позицию 8. Формируем новую вершину стека s5 = s3
   
   "8".
   
   
   Строка s5 содержит нули только в позициях 1, 2, 4, 8. Следовательно, найдено ПМВНК {1, 2, 4, 8} с пропускной способностью d1 + d2 + d4 + d8.
   
5. 
   Исключаем s5 из стека. Находим, что в s3 все нули исследованы. Исключаем s3 из стека. В s1 следующий нуль, подлежащий испытанию, занимает позицию 7. Формируем новую вершину стека — строку s6 = s1
   
   "7".
   
   
   Строка s6 не содержит нулей правее позиции 7. Исключаем s6 из стека.
   
6. 
   Следующий испытываемый нуль в s1 занимает позицию 8.
   
   Содержание раздела
   
   
   
   
   

   ---