Math
Théorie des graphes
Plus courts chemins, arbres couvrants et flots sur un même graphe, dessinés pendant qu'ils se calculent : l'onde de Dijkstra, les îles de Kruskal, les chemins d'Edmonds-Karp et la coupe qui égale le flot.
Ce qui se passe
Quarante nœuds lumineux dispersés au hasard, chacun relié à ses quatre plus proches et à ce qu'il faut pour que le graphe soit d'un seul tenant - cent arêtes, leurs longueurs pour poids et chacune une capacité de un à neuf. Trois questions, chacune résolue sous tes yeux pas à pas. Plus courts chemins : Dijkstra fixe les nœuds par ordre de distance à la source S, et l'ensemble fixé s'étend depuis S comme une onde - un nœud est fini dès que sa distance ne peut plus s'améliorer - jusqu'à ce que le puits T soit atteint et que son chemin s'allume avec les distances le long. Bellman-Ford, une méthode sans aucune file de priorité, est d'accord nœud par nœud, et l'inégalité triangulaire tient sur chaque arête. Arbre couvrant : Kruskal prend les arêtes de la plus légère à la plus lourde, garde celle qui relie deux îles (vert), rejette celle qui fermerait une boucle (rouge), et l'arbre est complet à N − 1 arêtes ; chaque arête rejetée est la plus lourde de la boucle qu'elle aurait fermée, et c'est pourquoi le choix glouton est le câblage le moins cher. Flot : Edmonds-Karp trouve le plus court chemin à capacité libre de S à T, y pousse le goulot et recommence, les arêtes se remplissant vers leurs capacités, jusqu'à ce qu'il ne reste plus de chemin - et alors la coupe s'allume entre ce que S atteint encore et le reste, et sa capacité égale le flot : max-flow = min-cut. Clique un nœud pour en faire la source, clic droit pour le puits ; déplace un nœud et chaque réponse est recalculée pour les nouvelles longueurs.
Équations du module
Équations graphe : N points dans [−1, 1]² tirés avec le dé commun (graine 3, N = 40) ; chacun relié à ses k = 4 plus proches voisins, plus l'arbre couvrant minimal euclidien pour que le graphe soit connexe ; 100 arêtes, poids = longueur, capacité 1 … 9 tirée avec le même dé ; S = nœud le plus à gauche (29), T = nœud le plus à droite (39) Dijkstra : d(S) = 0, les autres ∞ ; figer le nœud non figé de plus petit d, relaxer d(v) = min(d(v), d(u) + w(u, v)) pour ses voisins ; les nœuds figés ne s'améliorent jamais ; d(T) = 2.0906 en 6 arêtes ; Bellman–Ford (N − 1 tours sur toutes les arêtes) concorde à 10^−12 près ; d(v) ≤ d(u) + w(u, v) sur chaque arête Kruskal : arêtes par poids, garder e lorsque ses extrémités sont dans des composantes différentes (union–find) ; N − 1 = 39 gardées, 61 ignorées, poids 8.4480 ; la première arête ignorée est la douzième examinée ; propriété du cycle : une arête ignorée est au moins aussi lourde que chaque arête du chemin de l'arbre entre ses extrémités - donc l'arbre glouton est minimal Edmonds–Karp : capacité résiduelle c(u, v) − f(u, v) ; parcours en largeur de S à T sur les arêtes de capacité résiduelle, pousser le goulot b le long du chemin, f(u, v) += b, f(v, u) −= b ; recommencer jusqu'à ce qu'il n'y ait plus de chemin ; 13 chemins de goulots 2 1 2 1 1 1 1 1 2 1 1 1 1, flot 16 ; la coupe (nœuds que S atteint encore | le reste) a pour capacité 16, 35 nœuds du côté source ; conservation : flot net 0 en chaque nœud sauf S et T graphe simple : ni boucles ni arêtes parallèles ; Σ deg(v) = 2E ; circuit eulérien si et seulement si connexe et tous les degrés pairs, chemin eulérien si et seulement si exactement deux degrés sont impairs ; sur c composantes Kruskal garde N − c arêtes
