Math
Teoria grafów
Najkrótsze ścieżki, drzewa rozpinające i przepływy na jednym grafie, rysowane w trakcie obliczeń: fala Dijkstry, wyspy Kruskala, ścieżki Edmondsa-Karpa i przekrój równy przepływowi.
Co się dzieje
Czterdzieści świecących węzłów rozrzuconych losowo, każdy połączony z czterema najbliższymi i z tym, czego trzeba, by graf był jedną całością - sto krawędzi, ich długości to wagi, a każda ma przepustowość od jednego do dziewięciu. Trzy pytania, każde rozwiązywane na twoich oczach krok po kroku. Najkrótsze ścieżki: Dijkstra zamyka węzły w kolejności odległości od źródła S, a zbiór zamkniętych rozchodzi się od S jak fala - węzeł jest gotowy w chwili, gdy jego odległości nie da się już poprawić - aż osiągnięty zostanie ujście T i jego ścieżka rozświetli się z odległościami wzdłuż niej. Bellman-Ford, metoda bez żadnej kolejki priorytetowej, zgadza się węzeł w węzeł, a nierówność trójkąta zachodzi na każdej krawędzi. Drzewo rozpinające: Kruskal bierze krawędzie od najlżejszej, zachowuje tę, która łączy dwie wyspy (zieloną), odrzuca tę, która zamknęłaby pętlę (czerwoną), a drzewo jest gotowe przy N − 1 krawędziach; każda odrzucona krawędź jest najcięższa na pętli, którą by zamknęła, dlatego wybór zachłanny to najtańsze okablowanie. Przepływ: Edmonds-Karp znajduje najkrótszą ścieżkę z wolną przepustowością z S do T, przepycha nią wąskie gardło i powtarza, krawędzie wypełniają się do swoich przepustowości, aż ścieżek zabraknie - i wtedy rozświetla się przekrój między tym, do czego S wciąż sięga, a resztą, a jego przepustowość równa się przepływowi: max-flow = min-cut. Kliknięcie węzła czyni go źródłem, prawy klik ujściem; przeciągnij węzeł, a każda odpowiedź zostanie przeliczona dla nowych długości.
Równania modułu
Równania graf: N punktów w [−1, 1]² ze wspólnej kostki (ziarno 3, N = 40); każdy połączony ze swoimi k = 4 najbliższymi, plus euklidesowe minimalne drzewo rozpinające, aby graf był spójny; 100 krawędzi, waga = długość, przepustowość 1 … 9 z tej samej kostki; S = skrajnie lewy wierzchołek (29), T = skrajnie prawy (39) Dijkstra: d(S) = 0, pozostałe ∞; zatwierdź niezatwierdzony wierzchołek o najmniejszym d, zrelaksuj d(v) = min(d(v), d(u) + w(u, v)) dla jego sąsiadów; zatwierdzone wierzchołki już się nie poprawiają; d(T) = 2.0906 po 6 krawędziach; Bellman–Ford (N − 1 rund po wszystkich krawędziach) zgadza się z dokładnością 10^−12; d(v) ≤ d(u) + w(u, v) na każdej krawędzi Kruskal: krawędzie według wagi, zachowaj e, gdy jej końce leżą w różnych składowych (struktura zbiorów rozłącznych); N − 1 = 39 zachowanych, 61 pominiętych, waga 8.4480; pierwsza pominięta krawędź jest 12. rozważaną; własność cyklu: pominięta krawędź jest co najmniej tak ciężka jak każda krawędź na ścieżce w drzewie między jej końcami - więc zachłanne drzewo jest minimalne Edmonds–Karp: przepustowość rezydualna c(u, v) − f(u, v); przeszukiwanie wszerz od S do T po krawędziach z przepustowością rezydualną, przepchnij wąskie gardło b wzdłuż ścieżki, f(u, v) += b, f(v, u) −= b; powtarzaj, aż nie będzie ścieżki; 13 ścieżek z wąskimi gardłami 2 1 2 1 1 1 1 1 2 1 1 1 1, przepływ 16; przekrój (wierzchołki, do których S wciąż dociera | reszta) ma przepustowość 16, a po stronie źródła jest 35 wierzchołków; zachowanie: przepływ netto 0 w każdym wierzchołku oprócz S i T graf prosty: bez pętli, bez krawędzi wielokrotnych; Σ deg(v) = 2E; cykl Eulera istnieje wtedy i tylko wtedy, gdy graf jest spójny i każdy stopień jest parzysty, ścieżka Eulera wtedy i tylko wtedy, gdy dokładnie dwa stopnie są nieparzyste; przy c składowych Kruskal zachowuje N − c krawędzi
