Math
Teoria dei grafi
Cammini minimi, alberi ricoprenti e flussi su uno stesso grafo, disegnati mentre si calcolano: l'onda di Dijkstra, le isole di Kruskal, i cammini di Edmonds-Karp e il taglio che eguaglia il flusso.
Cosa succede
Quaranta nodi luminosi sparsi a caso, ognuno unito ai suoi quattro più vicini e a quanto serve perché il grafo sia un pezzo solo - cento archi, le loro lunghezze sono i pesi e ognuno ha una capacità da uno a nove. Tre domande, ognuna risolta davanti a te un passo alla volta. Cammini minimi: Dijkstra chiude i nodi in ordine di distanza dalla sorgente S, e l'insieme chiuso cresce da S come un'onda - un nodo è finito nell'istante in cui la sua distanza non può più migliorare - finché il pozzo T è raggiunto e il suo cammino si accende con le distanze lungo di esso. Bellman-Ford, un metodo senza alcuna coda di priorità, concorda nodo per nodo, e la disuguaglianza triangolare vale su ogni arco. Albero ricoprente: Kruskal prende gli archi dal più leggero al più pesante, tiene quello che unisce due isole (verde), scarta quello che chiuderebbe un ciclo (rosso), e l'albero è completo con N − 1 archi; ogni arco scartato è il più pesante del ciclo che avrebbe chiuso, ed è per questo che la scelta golosa è il cablaggio più economico. Flusso: Edmonds-Karp trova il cammino più corto con capacità libera da S a T, vi spinge il collo di bottiglia e ripete, gli archi si riempiono verso le loro capacità, finché non resta cammino - e allora si accende il taglio fra ciò che S raggiunge ancora e il resto, e la sua capacità eguaglia il flusso: max-flow = min-cut. Clic su un nodo lo rende sorgente, clic destro pozzo; trascina un nodo e ogni risposta si ricalcola per le nuove lunghezze.
Equazioni del modulo
Equazioni grafo: N punti in [−1, 1]² dal dado condiviso (seme 3, N = 40); ciascuno collegato ai suoi k = 4 più vicini, più l'albero di copertura minimo euclideo perché il grafo sia connesso; 100 archi, peso = lunghezza, capacità 1 … 9 dallo stesso dado; S = nodo più a sinistra (29), T = nodo più a destra (39) Dijkstra: d(S) = 0, gli altri ∞; si fissa il nodo non fissato con d minima, si rilassa d(v) = min(d(v), d(u) + w(u, v)) per i suoi vicini; i nodi fissati non migliorano mai; d(T) = 2.0906 su 6 archi; Bellman–Ford (N − 1 giri su tutti gli archi) concorda fino a 10^−12; d(v) ≤ d(u) + w(u, v) su ogni arco Kruskal: archi ordinati per peso, per ciascun arco e: lo si tiene quando i suoi estremi stanno in componenti diverse (union–find); N − 1 = 39 tenuti, 61 scartati, peso 8.4480; il primo arco scartato è il numero 12 tra quelli considerati; proprietà del ciclo: un arco scartato è pesante almeno quanto ogni arco del cammino nell'albero tra i suoi estremi - perciò l'albero goloso è minimo Edmonds–Karp: capacità residua c(u, v) − f(u, v); ricerca in ampiezza da S a T sugli archi con capacità residua, si spinge il collo di bottiglia b lungo il cammino, f(u, v) += b, f(v, u) −= b; si ripete finché non c'è alcun cammino; 13 cammini con colli di bottiglia 2 1 2 1 1 1 1 1 2 1 1 1 1, flusso 16; il taglio (nodi che S raggiunge ancora | il resto) ha capacità 16, 35 nodi dal lato della sorgente; conservazione: flusso netto 0 in ogni nodo tranne S e T grafo semplice: senza cappi, senza archi paralleli; Σ deg(v) = 2E; circuito euleriano se e solo se connesso e con ogni grado pari, cammino euleriano se e solo se esattamente due gradi sono dispari; su c componenti Kruskal tiene N − c archi
