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