Math
Teoría de grafos
Caminos más cortos, árboles de expansión y flujos en un mismo grafo, dibujados mientras se calculan: la onda de Dijkstra, las islas de Kruskal, los caminos de Edmonds-Karp y el corte que iguala al flujo.
Qué ocurre
Cuarenta nodos luminosos esparcidos al azar, cada uno unido a sus cuatro más cercanos y a lo que haga falta para que el grafo sea una sola pieza - cien aristas, sus longitudes son los pesos y cada una tiene una capacidad de uno a nueve. Tres preguntas, cada una respondida ante ti paso a paso. Caminos más cortos: Dijkstra cierra los nodos en orden de distancia a la fuente S, y el conjunto cerrado crece desde S como una onda - un nodo queda terminado en cuanto su distancia ya no puede mejorar - hasta que se alcanza el sumidero T y su camino se ilumina con las distancias a lo largo. Bellman-Ford, un método sin cola de prioridad alguna, coincide nodo a nodo, y la desigualdad triangular se cumple en cada arista. Árbol de expansión: Kruskal toma las aristas de la más ligera a la más pesada, conserva la que une dos islas (verde), descarta la que cerraría un ciclo (rojo), y el árbol queda completo con N − 1 aristas; cada arista descartada es la más pesada del ciclo que habría cerrado, y por eso la elección voraz es el cableado más barato. Flujo: Edmonds-Karp halla el camino más corto con capacidad libre de S a T, empuja el cuello de botella por él y repite, las aristas se llenan hacia sus capacidades, hasta que no queda camino - y entonces se ilumina el corte entre lo que S aún alcanza y el resto, y su capacidad iguala al flujo: max-flow = min-cut. Clic en un nodo lo hace fuente, clic derecho sumidero; arrastra un nodo y cada respuesta se recalcula para las nuevas longitudes.
Ecuaciones del módulo
Ecuaciones grafo: N puntos en [−1, 1]² del dado compartido (semilla 3, N = 40); cada uno unido a sus k = 4 más cercanos, más el árbol generador mínimo euclídeo para que el grafo sea conexo; 100 aristas, peso = longitud, capacidad 1 … 9 del mismo dado; S = nodo más a la izquierda (29), T = el más a la derecha (39) Dijkstra: d(S) = 0, los demás ∞; se fija el nodo no fijado de menor d, se relaja d(v) = min(d(v), d(u) + w(u, v)) para sus vecinos; los nodos fijados nunca mejoran; d(T) = 2.0906 en 6 aristas; Bellman–Ford (N − 1 rondas sobre todas las aristas) coincide hasta 10^−12; d(v) ≤ d(u) + w(u, v) en cada arista Kruskal: aristas por peso, se conserva e cuando sus extremos están en componentes distintas (conjuntos disjuntos); N − 1 = 39 conservadas, 61 omitidas, peso 8.4480; la primera arista omitida es la duodécima considerada; propiedad del ciclo: una arista omitida pesa al menos tanto como cada arista del camino del árbol entre sus extremos - así que el árbol voraz es mínimo Edmonds–Karp: capacidad residual c(u, v) − f(u, v); búsqueda en anchura de S a T por aristas con capacidad residual, se empuja el cuello de botella b por el camino, f(u, v) += b, f(v, u) −= b; se repite hasta que no haya camino; 13 caminos con cuellos de botella 2 1 2 1 1 1 1 1 2 1 1 1 1, flujo 16; el corte (nodos que S aún alcanza | el resto) tiene capacidad 16, 35 nodos en el lado de la fuente; conservación: flujo neto 0 en todo nodo salvo S y T grafo simple: sin lazos, sin aristas paralelas; Σ deg(v) = 2E; circuito euleriano si y solo si es conexo y todos los grados son pares, camino euleriano si y solo si exactamente dos grados son impares; con c componentes Kruskal conserva N − c aristas
