Math
Теория графов
Кратчайшие пути, остовные деревья и потоки на одном графе, нарисованные по мере счёта: рябь Дейкстры, острова Краскала, пути Эдмондса–Карпа и разрез, равный потоку.
Что происходит
Сорок светящихся узлов, разбросанных наугад, каждый соединён с четырьмя ближайшими и с тем, что нужно, чтобы граф был одним куском — сто рёбер, их длины — веса, и у каждого пропускная способность от одного до девяти. Три вопроса, каждый решается у тебя на глазах по шагу. Кратчайшие пути: Дейкстра закрывает узлы в порядке расстояния от источника S, и закрытое множество расходится от S как рябь — узел закрыт в тот миг, когда его расстояние уже нельзя улучшить, — пока не достигнут сток T и его путь не загорится с расстояниями вдоль него. Беллман–Форд, метод вовсе без очереди с приоритетом, согласен узел в узел, а неравенство треугольника держится на каждом ребре. Остовное дерево: Краскал берёт рёбра от лёгких к тяжёлым, оставляет то, что соединяет два острова (зелёное), отбрасывает то, что замкнуло бы петлю (красное), и дерево готово при N − 1 рёбрах; каждое отброшенное ребро — самое тяжёлое на петле, которую оно замкнуло бы, потому жадный выбор и есть самая дешёвая проводка. Поток: Эдмондс–Карп находит кратчайший путь со свободной пропускной способностью от S к T, проталкивает по нему узкое место и повторяет, рёбра наполняются к своим пропускным способностям, пока путей не останется — и тогда загорается разрез между тем, до чего S ещё дотягивается, и остальным, и его пропускная способность равна потоку: max-flow = min-cut. Клик по узлу делает его источником, правый клик — стоком, потяни узел — и все ответы пересчитаются под новые длины.
Уравнения модуля
Уравнения граф: N точек в [−1, 1]² от общего генератора (зерно 3, N = 40); каждая соединена с k = 4 ближайшими, плюс евклидово минимальное остовное дерево, чтобы граф был связным; 100 рёбер, вес = длина, пропускная способность 1 … 9 от того же генератора; S = самая левая вершина (29), T = самая правая (39) Дейкстра: d(S) = 0, остальные ∞; фиксируем нефиксированную вершину с наименьшим d, релаксируем d(v) = min(d(v), d(u) + w(u, v)) для её соседей; зафиксированные вершины больше не улучшаются; d(T) = 2.0906 по 6 рёбрам; Беллман–Форд (N − 1 раундов по всем рёбрам) согласуется до 10^−12; d(v) ≤ d(u) + w(u, v) на каждом ребре Краскал: рёбра в порядке возрастания веса, оставляем e, когда его концы лежат в разных компонентах (система непересекающихся множеств); N − 1 = 39 оставлено, 61 пропущено, вес 8.4480; первое пропущенное ребро - двенадцатое из рассмотренных; свойство цикла: пропущенное ребро не легче любого ребра на пути в дереве между его концами - значит, жадное дерево минимально Эдмондс–Карп: остаточная пропускная способность c(u, v) − f(u, v); поиск в ширину от S до T по рёбрам с остаточной пропускной способностью, пропускаем по найденному пути поток b, равный его узкому месту, f(u, v) += b, f(v, u) −= b; повторяем, пока есть путь; 13 путей с узкими местами 2 1 2 1 1 1 1 1 2 1 1 1 1, поток 16; разрез (вершины, достижимые из S | остальные) имеет пропускную способность 16, 35 вершин на стороне истока; сохранение: чистый поток 0 в каждой вершине, кроме S и T простой граф: без петель и кратных рёбер; Σ deg(v) = 2E; эйлеров цикл существует тогда и только тогда, когда граф связен и все степени чётны, эйлеров путь - тогда и только тогда, когда ровно две степени нечётны; при c компонентах Краскал оставляет N − c рёбер
