ArithmétiqueObjet mathématique · Glossaire
Graphe pondéré
Un graphe pondéré est un graphe (orienté ou non) dans lequel chaque arête ou arc est associé à un nombre appelé poids ou coût. Ces poids peuvent représenter des distances, des durées, des capacités ou des coûts selon le contexte applicatif. Les algorithmes classiques de plus court chemin comme Dijkstra ou Bellman-Ford sont définis sur des graphes pondérés. Dans un graphe non orienté pondéré et connexe, un arbre couvrant de poids minimum peut être calculé par les algorithmes de Kruskal ou Prim.
Sommaire
Ce que vous allez apprendre
- Identifier les sommets, liaisons et poids d'un graphe pondéré.
- Calculer et contrôler le poids minimal d'un chemin sur un exemple à quatre sommets.
- Choisir entre Dijkstra, Bellman-Ford, Kruskal et Prim selon le problème et les poids.
- Repérer les cycles négatifs, les sommets inaccessibles et les capacités non additives.
En clair
Imaginez quatre villes reliées par des routes. Sur chaque route, un nombre indique une distance, une durée ou un prix. Le dessin montre quelles villes communiquent ; les nombres permettent de comparer les itinéraires.
Ce réseau est un graphe pondéré. Un trajet court en nombre de routes n'est pas forcément celui dont le poids total est le plus faible : il faut additionner les valeurs rencontrées.
Définition
Un graphe pondéré comporte un ensemble de sommets, des liaisons entre certains sommets et une fonction de poids. Cette fonction associe un nombre à chaque liaison. Dans un graphe non orienté, les liaisons sont des arêtes ; dans un graphe orienté, ce sont des arcs parcourus dans un sens déterminé.
Le sens d'un poids dépend du modèle : distance, durée et dépense s'additionnent le long d'un chemin, tandis qu'une capacité ne se combine pas de la même façon. Pour un chemin, son poids total est généralement la somme des poids de ses liaisons. Deux arêtes distinctes peuvent porter le même poids, et les poids ne sont pas nécessairement positifs sauf si l'algorithme choisi l'exige.
Cette structure permet notamment de chercher un chemin de poids minimal ou un arbre couvrant de poids minimal. Dijkstra demande des poids non négatifs ; Bellman-Ford accepte des poids négatifs, sous réserve qu'aucun cycle négatif atteignable ne rende le minimum indéfini. Kruskal et Prim traitent le problème distinct de l'arbre couvrant minimal dans un graphe non orienté pondéré.
De quoi c'est fait
Quatre éléments décrivent la structure. Les sommets représentent les objets étudiés. Les arêtes, ou les arcs si le graphe est orienté, indiquent les liaisons admises. Les poids donnent une valeur à chaque liaison. Enfin, l'éventuelle orientation fixe le sens autorisé de parcours des arcs.
Un poids n'existe donc pas indépendamment d'une liaison, et un chemin dépend à la fois des liaisons présentes et de leur sens. Sommets, liaisons, poids et règle de combinaison des valeurs permettent de calculer le poids d'un chemin ; dans le cas additif, on additionne les poids de ses liaisons. L'emplacement des sommets sur la page, la longueur dessinée des traits et leur couleur ne définissent pas le graphe, sauf si le modèle leur attribue explicitement cette signification.
Un exemple, pas à pas
On considère un réseau non orienté de sommets A, B, C et D. Les cinq arêtes ont les poids suivants : A–B vaut 4, A–C vaut 1, C–B vaut 2, B–D vaut 1 et C–D vaut 5. On cherche un chemin de poids minimal de A à D.
1. Le chemin A–B–D a pour poids 4 + 1 = 5.
2. Le chemin A–C–D a pour poids 1 + 5 = 6.
3. Le chemin A–C–B–D a pour poids 1 + 2 + 1 = 4.
4. Le chemin A–B–C–D a pour poids 4 + 2 + 5 = 11.
5. Parmi ces quatre chemins simples, le plus petit total est donc 4.
2. Le chemin A–C–D a pour poids 1 + 5 = 6.
3. Le chemin A–C–B–D a pour poids 1 + 2 + 1 = 4.
4. Le chemin A–B–C–D a pour poids 4 + 2 + 5 = 11.
5. Parmi ces quatre chemins simples, le plus petit total est donc 4.
Le chemin minimal est A–C–B–D, de poids 4. Un contrôle consiste à partir de A avec un total nul : les meilleurs totaux successifs vers C, B puis D sont 1, 3 et 4. La figure matérialise en rouge ces trois arêtes et laisse les deux autres en noir.
En pratique
Pour préparer un itinéraire, les sommets représentent des lieux et les poids des distances ou des durées. On choisit un chemin minimal ; si toutes les liaisons ont un coût non négatif, Dijkstra convient.
Dans un réseau de transport ou de télécommunication, un poids peut mesurer un délai ou une dépense. Si certaines valeurs négatives modélisent un gain, Bellman-Ford remplace Dijkstra et permet aussi de détecter un cycle négatif atteignable.
Pour relier tous les sites avec un coût total minimal, on ne cherche plus un trajet entre deux sommets. On construit un arbre couvrant minimal avec Kruskal ou Prim, à condition que le graphe non orienté soit connexe.
À ne pas confondre
Graphe non pondéré. Il indique seulement si une liaison existe. Si A–B et A–C sont présentes sans valeur associée, on peut compter les arêtes, mais pas comparer une distance de 4 à une distance de 1.
Graphe orienté. L'orientation fixe un sens de parcours ; la pondération fixe une valeur. Un graphe peut être orienté sans être pondéré, pondéré sans être orienté, ou posséder les deux propriétés.
Arbre couvrant minimal. Il relie tous les sommets sans cycle et minimise le poids total des arêtes retenues. Un plus court chemin ne relie que deux sommets imposés : dans l'exemple, A–C–B–D répond à cette seconde question.
Limites et pièges
Poids négatif. Dès qu'une arête ou un arc a un poids inférieur à 0, Dijkstra n'offre plus la garantie attendue. Il faut employer un algorithme adapté, tel Bellman-Ford. Dans un graphe non orienté, une arête négative permet en outre des allers-retours de poids toujours plus faible si les parcours répétés sont admis.
Cycle négatif atteignable. Si un cycle de poids total inférieur à 0 est accessible depuis le départ et mène à l'arrivée, il n'existe pas de plus petit poids : répéter le cycle diminue indéfiniment le total. Bellman-Ford sert alors à signaler ce blocage, pas à fournir un minimum.
Sommet inaccessible. L'absence de chemin n'équivaut pas à un chemin de poids 0. La distance est alors considérée comme infinie, et un graphe non connexe n'admet aucun arbre couvrant englobant tous ses sommets ; on obtient plutôt une forêt couvrante.
Capacité d'un réseau. Additionner les capacités d'un chemin est souvent une erreur : son débit est limité par l'arc le moins capacitaire. Avant tout calcul, il faut donc préciser ce que mesure le poids et la règle selon laquelle les valeurs se combinent.
Pour aller plus loin
algorithme de Moore-Dijkstra — Suivez la sélection progressive des distances minimales lorsque tous les poids sont non négatifs.
algorithme de Bellman-Ford — Étudiez les poids négatifs et la détection des cycles qui empêchent l'existence d'un minimum.
algorithme de Kruskal — Voyez comment sélectionner des arêtes légères sans former de cycle pour couvrir tous les sommets.
arbre couvrant — Distinguez la structure qui relie tous les sommets du chemin qui joint seulement deux sommets.
Graphe orienté et non-orienté — Approfondissez le rôle du sens des arcs, indépendamment de la présence de poids.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres