Un service de livraison veut relier son dépôt à plusieurs points de retrait. Avant de chercher le meilleur trajet, il faut décider ce que représente un point, une liaison et son coût. Cette décision paraît simple ; elle détermine pourtant les questions auxquelles le programme pourra répondre. Dans ce chapitre, nous construisons un modèle précis, puis nous apprenons à le lire sans confondre le dessin, les données et le problème posé.
Pour notre réseau fictif, A représente le dépôt et B, C, D, E, F des points de retrait. Une liaison indique qu'un déplacement direct est autorisé dans le modèle. Elle ne signifie pas nécessairement qu'une route droite existe sur une carte. Deux points dessinés loin peuvent être reliés à faible coût ; leur position graphique sert seulement à rendre le schéma lisible.
On conserve volontairement peu d'informations. Le modèle ne contient ni horaires, ni embouteillages, ni stocks. Si ces informations deviennent indispensables, il faut les ajouter explicitement. Un algorithme correct sur un modèle incomplet peut fournir une mauvaise décision pratique. Commencez donc par écrire une phrase : « Un sommet représente…, une liaison signifie…, le coût mesure… ». Cette phrase protège contre bien des erreurs.
Un abonnement à un compte social est naturellement orienté : suivre quelqu'un n'implique pas être suivi en retour. Une liaison entre deux ordinateurs peut être modélisée sans orientation si la communication fonctionne dans les deux sens avec les mêmes contraintes. Il faut choisir selon le problème étudié, et non selon l'habitude de dessiner des flèches.
Dans notre exemple principal, les liaisons sont non orientées et les poids sont des unités de coût abstraites. Ce ne sont pas des kilomètres entre villes réelles. Le coût AB vaut 4 et le coût AC vaut 2. Nous supposerons que les coûts s'additionnent le long d'un trajet. Cette hypothèse conviendrait à une dépense, mais pas automatiquement à une probabilité ou à un débit : toutes les valeurs numériques ne s'additionnent pas.
Notre réseau possède les arêtes AB, AC, BC, BD, CD, CE, DE, DF et EF. Les voisins de A sont B et C. Les voisins de D sont B, C, E et F : son degré vaut donc 4. Les poids n'interviennent pas dans ce décompte. Une liaison coûteuse compte autant qu'une liaison bon marché.
| Sommet | Voisins | Degré |
|---|---|---|
| A | B, C | 2 |
| B | A, C, D | 3 |
| C | A, B, D, E | 4 |
| D | B, C, E, F | 4 |
| E | C, D, F | 3 |
| F | D, E | 2 |
La somme des degrés vaut 18, soit deux fois les 9 arêtes. Pourquoi ? Chaque arête contribue une extrémité à chacun de ses deux sommets. On compte donc chaque liaison deux fois en parcourant tous les voisinages. Une boucle non orientée apporte également deux extrémités au même sommet. Dans le cas orienté, chaque arc apporte une unité au total des degrés entrants et une au total des degrés sortants.
Le trajet A–B–D–F comporte 3 arêtes et coûte 15 unités. Le trajet A–C–B–D–E–F comporte 5 arêtes et coûte 13 unités. Le premier comporte moins d'étapes, mais le second coûte moins cher. Cette différence explique pourquoi un même réseau appelle plusieurs algorithmes : « moins de liaisons » et « coût total minimal » sont deux objectifs distincts.
Notre réseau est connexe. Pour le vérifier, il suffit de partir de A et de découvrir tous les sommets ; nous automatiserons cette exploration avec BFS et DFS. Dans un graphe orienté, être relié en oubliant les flèches ne garantit pas de pouvoir circuler dans les deux sens. On parle de forte connexité lorsque chaque sommet du groupe peut atteindre tous les autres en respectant les arcs.
Supprimer des liaisons peut conserver l'accès à tous les points tout en évitant les cycles. On obtient alors un arbre couvrant, c'est-à-dire un arbre qui garde tous les sommets du graphe de départ. Il ne faut pas confondre cette structure avec un trajet de livraison : un arbre décrit des liaisons installées, pas l'ordre dans lequel un véhicule les emprunte.
Deux autres questions classiques concernent les parcours. Un parcours eulérien utilise chaque arête exactement une fois. Un chemin hamiltonien visite chaque sommet exactement une fois. On compte les arêtes dans le premier cas et les sommets dans le second. Les critères et les difficultés algorithmiques diffèrent profondément ; connaître le degré des sommets ne suffit pas à résoudre toutes les questions de visite.
Nous noterons n le nombre de sommets et m le nombre de liaisons. Cette convention servira à mesurer les ressources des algorithmes. Les étiquettes doivent rester stables : renommer C au milieu d'un calcul revient à modifier les données. Pour comparer des traces, nous examinerons les voisins par ordre alphabétique. Cet ordre rend les résultats reproductibles ; il n'est pas une règle de circulation.
Définir les sommets et leur signification
Définir les liaisons autorisées
Préciser orientation, poids et unité
Vérifier les extrémités de chaque liaison
Formuler exactement la question à résoudreLorsqu'un résultat surprend, revenez à cette préparation avant d'accuser l'algorithme. Un arc oublié peut rendre un sommet inaccessible. Une arête enregistrée dans un seul sens peut transformer involontairement le réseau en graphe orienté. Une valeur absente n'est pas un coût nul. Le prochain chapitre montre comment stocker ces distinctions sans ambiguïté.
Un réseau de comptes représente « u suit v ». Faut-il orienter les liaisons ? Que peut-on conclure d'une liaison u → v ?
Il faut un arc orienté. Il indique uniquement que u suit v. Pour conclure que v suit u, il faut vérifier la présence de l'arc inverse. La proximité des comptes sur un dessin ne fournit aucune information supplémentaire.
Retrouvez le degré de C et expliquez pourquoi la somme des degrés compte chaque arête deux fois.
C est relié à A, B, D et E : son degré vaut 4. Une arête non orientée possède deux extrémités. Le décompte global ajoute une contribution à chaque extrémité, donc deux contributions par arête, indépendamment des poids.
Comparez A–B–D–F et A–C–B–D–E–F selon le nombre d'arêtes puis selon le coût.
Le premier trajet utilise 3 arêtes et coûte 4 + 5 + 6 = 15. Le second utilise 5 arêtes et coûte 2 + 1 + 5 + 2 + 3 = 13. Minimiser les étapes ne minimise donc pas nécessairement la dépense.
Une équipe veut installer des câbles reliant tous les bâtiments avec un coût total minimal. Cherche-t-elle un chemin hamiltonien ?
Non. Elle cherche un ensemble de liaisons couvrant les bâtiments, donc un arbre couvrant minimal si le graphe est non orienté et connexe. Un chemin hamiltonien impose un ordre de visite sans répétition des sommets, contrainte absente du problème d'installation.
Questions / Réponses
Ajouter un commentaire