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; перше пропущене ребро - 12-те з розглянутих; властивість циклу: пропущене ребро щонайменше таке ж важке, як кожне ребро на шляху в дереві між його кінцями - тому жадібне дерево мінімальне Едмондс–Карп: залишкова пропускна здатність 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 ребер
