Routes, canalisations, câbles, chaînes logistiques : tout réseau se dessine avec des points et des flèches. Sur un même réseau, quatre questions classiques : le chemin le plus court, le réseau le moins cher, le plus grand débit, l'acheminement le plus économique.
Un réseau, c'est un graphe dont les liaisons portent des nombres : une longueur, un coût, une capacité. Les marchandises partent du dépôt S et doivent atteindre le marché T. Le même dessin sert pour toute la page.
Le réseau en fonctionnement : 20 unités par jour acheminées au moindre coût (planche 5). L'épaisseur de chaque flèche est proportionnelle au flux qui y passe.
Le réseau et ses chiffres sont inventés. Les résultats sont calculés sur place dans votre navigateur et confrontés à une seconde méthode : énumération complète, ou programme linéaire. Cette page complète La théorie des graphes et Le plus court chemin de ce cahier : ici, un seul réseau sert aux quatre problèmes, pour montrer qu'ils forment une même famille.
Planche 1
Sommets, arcs, chemins et capacités
Les sommets sont les lieux : dépôt, carrefours, marché. Les arcs sont les liaisons, orientées par une flèche : on ne va que dans un sens. Un chemin est une suite d'arcs bout à bout. Chaque arc porte un coût (ici, en euros par unité transportée) et une capacité (le nombre d'unités qu'il peut porter par jour).
Cliquez sur un sommet de départ, puis sur un sommet d'arrivée. Le nombre affiché sur chaque arc dépend du bouton choisi ci-dessous.
–
Sommets ; arcs–
Arcs sortants ; entrants du départ–
Chemins sans boucle du départ à l'arrivée–
Le moins coûteux, et son goulot–
Le plus large (meilleur goulot), et son coût–
Chemin affiché : coût ; goulot–
Ce qu'il faut retenir. Le goulot d'un chemin est la plus petite capacité de ses arcs : c'est tout ce qu'il peut faire passer. De S à T, trois chemins coûtent 15 €, et aucun ne laisse passer plus de 5 unités ; le plus large en laisse passer 8, mais coûte 21 €. Chaque question a son optimum, et chaque problème de réseau commence par choisir le nombre qu'on regarde.
Planche 2
Plus court chemin : Dijkstra et Bellman-Ford
Deux méthodes pour le chemin le moins coûteux depuis S vers tous les sommets. Dijkstra fixe définitivement, à chaque étape, le sommet non fixé le plus proche : c'est rapide, mais suppose des coûts positifs. Bellman-Ford passe en revue tous les arcs, encore et encore, tant qu'une étiquette s'améliore : c'est plus lent, mais cela accepte les coûts négatifs.
Dijkstra. Vert : sommets fixés. Orange : étiquettes provisoires. Trait épais : l'arbre des meilleurs prédécesseurs.
Bellman-Ford. Les arcs qui viennent d'améliorer une étiquette sont en orange, pendant la passe affichée.
–
Coût de S à T : Dijkstra–
Coût de S à T : Bellman-Ford–
Contrôle : meilleur des 21 chemins énumérés–
Arcs examinés : Dijkstra ; Bellman-Ford–
Sommets où Dijkstra se trompe–
Pourquoi Dijkstra se trompe. Il fixe B à 3 avant d'avoir regardé A, car A est plus loin (4). Avec un arc A → B à −3, le passage par A coûte 4 − 3 = 1, mais B est déjà fixé : Dijkstra ne revient jamais en arrière, et toute la suite (C, D, E, F, T) en hérite. Bellman-Ford corrige à la passe suivante. Avec des coûts positifs, les deux méthodes donnent exactement les mêmes distances, et Dijkstra examine chaque arc une seule fois.
Planche 3
Arbre couvrant minimal : concevoir un réseau au moindre coût
Il faut maintenant construire le réseau : relier les huit sites par un câble, sans se soucier du sens, en payant le moins possible. Le nombre sur chaque liaison est son coût de construction. La solution est un arbre : un réseau connexe sans boucle, avec exactement 7 liaisons pour 8 sites. Deux méthodes gloutonnes le trouvent, et c'est l'un des rares cas où la gourmandise est optimale.
Kruskal : on trie les liaisons de la moins chère à la plus chère, et on les prend une à une, sauf si elle ferme une boucle.
Bleu : liaisons retenues. Rouge barré : liaison refusée, car ses deux bouts sont déjà reliés. Couleur des sommets : le morceau de réseau auquel ils appartiennent.
Prim : on part d'un site, et on ajoute à chaque étape la liaison la moins chère qui sort du réseau déjà construit.
Vert : sites déjà reliés. Pointillés orange : les liaisons candidates, qui sortent du réseau construit ; la moins chère est entourée. Cliquez sur un sommet pour changer de point de départ.
–
L'arbre le moins cher à construire n'est pas forcément agréable à utiliser : les trajets y font parfois de longs détours. Comparez trois réseaux. Cliquez ensuite sur une liaison pour simuler une panne.
Le réseau choisi. Une liaison cliquée tombe en panne (pointillés rouges) ; les sites coupés du reste passent en rouge.
Coût de construction–
Trajet moyen entre deux sites–
Trajet le plus long–
Liaisons dont la panne coupe le réseau–
Après la panne : morceaux de réseau–
Coût : Kruskal ; Prim–
Arbres couvrants possibles (déterminant de Kirchhoff)–
Contrôle : arbres énumérés un à un, le moins cher et le plus cher–
Ce qu'il faut retenir. Parmi 1 558 arbres possibles, coûtant de 18 à 48, les deux méthodes trouvent l'arbre à 18 sans les examiner. Mais un arbre n'a aucune redondance : la moindre panne coupe le réseau en deux, et certains trajets s'allongent. Un vrai réseau ajoute des liaisons de secours. L'arbre couvrant minimal sert donc de point de départ, pas de réponse définitive.
Planche 4
Flot maximal et coupe minimale
Combien d'unités par jour peut-on faire passer de S à T, toutes routes confondues ? Le flot respecte deux règles : jamais plus que la capacité sur un arc, et en chaque sommet intermédiaire, autant d'unités qui sortent que d'unités qui entrent. La méthode de Ford et Fulkerson cherche un chemin où il reste de la place, y pousse le plus possible, et recommence.
Chaque arc affiche flux / capacité. Rouge : arc saturé. Orange : le chemin augmentant de l'étape. À la fin, la courbe pointillée sépare les sommets encore atteignables depuis S. Cliquez sur un arc pour lui ajouter 3 de capacité.
Les 64 façons de séparer S de T, rangées par capacité. Chaque barre est la capacité d'une coupe : la somme des arcs qui vont du côté de S vers le côté de T. Trait rouge : la valeur du flot.
–
Flot acheminé–
Chemins augmentants utilisés–
Coupe minimale (arcs coupés)–
Contrôle : 64 coupes énumérées, la plus petite ; nombre de coupes minimales–
Le théorème flot maximal – coupe minimale. Le plus grand flot est égal à la plus petite capacité d'une coupe. La coupe minimale est donc le vrai goulot du réseau. Le tableau le confirme : agrandir un arc hors de toute coupe minimale ne sert à rien, même s'il est saturé. Agrandir un arc de la coupe aide, mais seulement jusqu'à ce qu'une autre coupe devienne limitante. Ici, A → C et B → C ne rapportent rien, car une autre coupe, de même capacité 30, ne les contient pas.
Planche 5
Flot à coût minimal : acheminer des marchandises
Le marché T demande D unités par jour. Il faut les faire venir de S au moindre coût, sans dépasser les capacités. C'est le problème le plus général de la page : il contient les autres. La méthode envoie la marchandise par le chemin le moins coûteux où il reste de la place, puis par le suivant, en autorisant à défaire un envoi antérieur si cela coûte moins cher.
Le plan d'acheminement : épaisseur selon le flux, flux / capacité sur chaque arc utilisé. Les points circulent à une vitesse proportionnelle au flux. Rouge : arc saturé.
Coût total selon la demande (bleu) : il est formé de segments de plus en plus pentus. En dessous, le coût de la dernière unité (escalier violet). Au-delà de 30, aucun plan n'existe.
–
Coût total par jour–
Coût moyen par unité–
Coût de la dernière unité–
Chemins utilisés successivement–
Contrôle : même problème écrit en programme linéaire, écart–
En réglant les données du flot à coût minimal, on retrouve les problèmes précédents. Les chiffres ci-dessous sont recalculés par les deux méthodes, à chaque fois.
La même courbe de coût, lue autrement : sa première pente est le plus court chemin, sa longueur est le flot maximal, et chaque changement de pente marque la saturation d'un arc.
Ce que dit la courbe. Le coût d'une unité de plus ne fait que monter : 15 € tant que le chemin le plus court a de la place, puis 17, 18, et enfin 21 €. Chaque saut correspond à un arc qui se remplit, et à un détour plus cher. Le coût moyen cache cette hausse ; le coût marginal la montre. Un transporteur qui facture au coût moyen perd de l'argent sur les dernières unités. Et quand le réseau ne peut plus rien faire passer, ce n'est plus une question de prix : c'est la coupe minimale de la planche 4.
Ce qu'il faut garder
Un vocabulaire
Sommets, arcs, chemins ; un coût et une capacité sur chaque arc. Le goulot d'un chemin est sa plus petite capacité, la coupe minimale est le goulot du réseau entier.
Des méthodes rapides
Dijkstra, Bellman-Ford, Prim, Kruskal, Ford-Fulkerson : aucune n'énumère les solutions. Chacune exploite la structure du réseau, et résout en un instant ce que l'énumération mettrait des siècles à faire sur un vrai réseau.
Une seule famille
Plus court chemin, flot maximal et transport sont des cas du flot à coût minimal, lui-même un programme linéaire aux solutions entières. Bien formuler, c'est reconnaître lequel on a devant soi.
Pour aller plus loin
Dans ce cahier.La théorie des graphes présente parcours, arbres et cycles ; Le plus court chemin approfondit Dijkstra, A* et le paradoxe de Braess ; Le problème de transport et Le problème d'affectation sont des flots à coût minimal particuliers ; Router et dimensionner un réseau de fibres applique ces idées aux télécommunications.
Sur les calculs. Le flot maximal utilise la variante d'Edmonds et Karp : on prend à chaque fois le chemin augmentant le plus court en nombre d'arcs. Le flot à coût minimal enchaîne des chemins de coût minimal dans le réseau résiduel, calculés par Bellman-Ford, car les arcs de retour ont un coût négatif. Le contrôle le réécrit en programme linéaire (conservation en chaque sommet, capacité sur chaque arc), résolu par le simplexe : avec des capacités entières, l'optimum est entier.