Потоки по лесу, единственность и линейный базис

Если можешь устранить листья и объяснить роль ранга, переходи к «Теперь сам».

Крючок: единственный ответ с отрицательной поставкой

Как думаешь, единственность решения балансов уже означает допустимость? Пусть две дуги A→B и B→A имеют множители два и 3/4, в A запас два, в B баланс ноль. Уравнения дают y=2x и x-(3/4)y=2, значит x=-4,y=-8. Решение единственно, но обе поставки отрицательны. Хорошесть дополненного дерева отвечает за алгебру, границы переменных - за допустимость. Эти проверки выполняют последовательно.

На что это похоже: сведение счетов к одному

Представь отделения компании, соединённые деревом переводов. У крайнего отделения только один канал: его задолженность однозначно определяет перевод по этому каналу. Убираешь закрытое отделение и переносишь остаток к соседу. После удаления всех листьев остаётся центральный счёт. Дополнительный канал замыкает цикл и даёт параметр, которым можно обнулить последний остаток.

Механизм: сначала учти фиксированные дуги

Используем остаточный дисбаланс e=b-(исходящий поток минус входящий преобразованный поток). Вначале e(i)=b(i). Для каждой дуги из U ставим x=u, уменьшаем e в начале на u и увеличиваем e в конце на μu. Дуги L остаются нулевыми. Затем на дополнительной дуге a→b ставим θ: e(a) уменьшаем на θ, e(b) увеличиваем на μθ. Теперь все e - выражения f+gθ.

Если лист j соединён с родителем i дугой j→i, задаём x=e(j), чтобы убрать весь его остаток исходящим потоком. Родителю добавляем μe(j), потому что такой приход уменьшает требуемый чистый уход. Если дуга направлена i→j, задаём x=-e(j)/μ: вход должен закрыть отрицательный остаток листа. Из e(i) вычитаем x, то есть прибавляем e(j)/μ. Знак в этом месте часто путают: при e(j)=-6 и μ=2 родитель отправляет три и его остаток уменьшается на три.

После удаления листа повторяем. В корне остаётся e(root)=f+gθ. Ставим θ=-f/g. Коэффициент g ненулевой ровно при несохраняющем единственном цикле. Подставляем θ в потоки и проверяем 0≤x≤u. Каждый лист удаляем один раз, поэтому вычисления на F линейны по числу вершин, а предварительный учёт U линейный по числу дуг.

Правило: базис определяет поток для любого b

Для квадратной матрицы базисных столбцов B нужен единственный ответ Bx=b при любом b. Это условие обратимости, то есть независимости столбцов и полного ранга. Для обобщённой сети столбец дуги содержит +1 у начала и -μ у конца. Для петли это один элемент 1-μ. Хороший дополненный лес даёт нужную обратимую матрицу. Требования x≥0 и x≤u проверяют уже после решения системы.

Разбор: удаляем лист с параметром

Есть корень A, вершина B, лист C. Дуги A→B с μ=2, B→A с μ=3/4 и B→C с μ=1/2. Балансы b(A)=-1,b(B)=0,b(C)=-2. Дополнительная дуга B→A несёт θ. После её учёта e(A)=-1+3θ/4,e(B)=-θ,e(C)=-2.

Лист C требует вход: x(B,C)=-(-2)/(1/2)=4. Поэтому e(B)=-θ-4. Лист B в оставшемся дереве получает поток от A, значит x(A,B)=-e(B)/2=θ/2+2. После его удаления корневой остаток равен -1+3θ/4-(θ/2+2)=θ/4-3. Приравниваем нулю: θ=12, x(A,B)=8, x(B,C)=4.

Проверка исходных балансов: A:8-(3/4)·12=-1; B:12+4-2·8=0; C:-(1/2)·4=-2. Если ёмкость B→A равна десяти, этот лес недопустим. Решение балансов правильное, но надо искать другую базисную структуру.

# forest_flow.py
from fractions import Fraction as F
b_a = F(-1)
b_b = F(0)
b_c = F(-2)
mu_ab = F(2)
mu_ba = F(3, 4)
mu_bc = F(1, 2)
# e(A) = -3 + theta/4 после устранения листьев.
f = F(-3)
g = F(1, 4)
theta = -f / g
x_ba = theta
x_bc = -b_c / mu_bc
x_ab = (theta + x_bc) / mu_ab
print(x_ab, x_ba, x_bc)
assert x_ab - mu_ba * x_ba == b_a
assert x_ba + x_bc - mu_ab * x_ab == b_b
assert -mu_bc * x_bc == b_c
print(x_ba <= 10)
# 8 12 4
# False

Разбор: матрица из двух столбцов

Для двух дуг A→B и B→A матрица равна [[1,-3/4],[-2,1]]. Её определитель равен 1-(3/4)·2=-1/2. Определитель двух на два - произведение главной диагонали минус произведение другой; ненулевое значение означает единственность решения для любого правого столбца b. Множитель цикла равен 1.5, поэтому выражение 1-μ(W) тоже ненулевое.

Заменим множитель B→A на 1/2. Определитель станет 1-1=0. Для b=(0,0) подойдёт любой x, y=2x; для b=(-2,0) решений нет. Это показывает обе причины, по которым сохраняющий цикл не базис при полном наборе независимых балансов: свобода там, где нужна единственность, и несовместность для некоторых b.

Теперь рассмотрим произвольный набор n дуг на n вершинах. Если он не состоит из хороших дополненных деревьев, либо какая-то компонента имеет меньше дуг, чем вершин, либо компонента имеет единственный сохраняющий цикл. Компонента с избытком циклов при общем счёте n вынуждает другую компоненту иметь дефицит дуг. Дерево с nᵢ-1 дугой не может дать ранг nᵢ; сохраняющий цикл тоже создаёт зависимость. Следовательно, такой набор не базис. Обратное уже доказали процедурой единственного вычисления потока на хорошем лесу.

Что ломается без предпосылки полного ранга

В обычной сети все μ=1. Сумма строк матрицы равна нулю, поэтому ранг не достигает n. Там нельзя искать обратимый набор из n столбцов и требовать несохраняющий цикл: его нет. Убирают одно избыточное равенство на связную компоненту и получают базисные деревья. В обобщённом алгоритме можно ввести искусственные петли с μ≠1, которые обеспечивают полный ранг расширенной системы. При исчезновении искусственного потока некоторые такие столбцы могут остаться нулевыми базисными переменными.

Зачем в работе

Эта связь даёт два способа проверить код: обходом леса и решением небольшой системы линейных уравнений. На малых сетях ответы должны совпасть. Если обход даёт другое число, ищи знак при входящем листе или пропущенный вклад U. Если оба способа дают отрицательную поставку, алгоритм не сломан: выбранный базис просто недопустим.

Теперь сам

На двух дугах с μ=2 и μ=3/4 поставь b(A)=-3,b(B)=0. Найди x,y и реши, допустим ли ответ при u(A,B)=5,u(B,A)=20. Ответ: y=2x, -x/2=-3, поэтому x=6,y=12. Первое ограничение нарушено. Хорошесть цикла и ненулевой определитель сохраняются, но структура не даёт допустимого потока.