TD 1 : Algorithmes de graphes, 30 exercices corrigés

Chaque lieu devient un sommet. Une liaison autorisée devient une arête non orientée, portant une dépense exprimée dans une unité commune. Pour les exemples du TD, cette unité est abstraite. On peut chercher un trajet de coût minimal entre deux lieux ou un ensemble de liaisons de coût total minimal couvrant tous les lieux. Le premier résultat est un chemin ; le second est un arbre couvrant minimal si le réseau est connexe. Utiliser les mêmes données ne rend pas ces deux objectifs identiques.

Les arêtes incidentes sont BD, CD, DE et DF. Les voisins sont donc B, C, E et F, et le degré de D vaut 4. Les valeurs 5, 8, 2 et 6 mesurent des coûts ; elles ne représentent pas des nombres de liaisons. Additionner ces valeurs ne donnerait pas le degré. Un contrôle global retrouve une somme des degrés de 18 pour les 9 arêtes du réseau, car chaque arête possède deux extrémités.

Non. Les positions graphiques ne font pas partie des poids de ce modèle. Les arêtes et leurs valeurs restant identiques, tous les trajets autorisés et leurs coûts restent identiques. Le plus court coût reste donc 13. Cette conclusion suppose que les poids sont les données explicites. Si un autre modèle calculait les poids à partir de coordonnées géographiques, modifier ces coordonnées changerait les données ; ce n'est pas la convention de notre réseau.

A atteint D par l'arc direct, mais aussi par A–B–C–D, qui coûte 3. D n'atteint pas A : aucun arc n'entre dans A. Le trajet inverse d'un chemin orienté n'est pas automatiquement autorisé. Même si les sommets sont reliés lorsque l'on oublie les flèches, les deux questions de trajet peuvent avoir des réponses différentes. Les cases AD et DA d'une matrice de distances ne sont donc pas nécessairement égales.

La première contrainte porte sur un parcours eulérien : les arêtes doivent être utilisées exactement une fois. La seconde porte sur un chemin hamiltonien : les sommets doivent être visités exactement une fois. Les contraintes ne comptent pas les mêmes objets. Un argument sur les degrés peut aider à étudier un parcours eulérien, mais ne résout pas automatiquement une question hamiltonienne. Il faut conserver la formulation précise et ne pas remplacer une visite des lieux par une utilisation des liaisons.

En non orienté, la liste de D contient (B, 5), (C, 8), (E, 2) et (F, 6). Les deux premières entrées proviennent des arêtes BD et CD, même si D est écrit en seconde position. Dans une interprétation orientée utilisant les sens écrits, seules DE et DF sortiraient de D. Il faudrait donc retirer les entrées vers B et C de sa collection de sorties, sans pour autant supprimer les arcs BD et CD du graphe.

La matrice contient 6 × 6 = 36 cases. Les 9 arêtes non orientées apparaissent chacune deux fois, soit 18 entrées de voisinage, plus les collections des 6 sommets. Ces objets n'ont pas nécessairement la même taille physique. Une entrée peut contenir une étiquette, un poids et des frais de gestion. On ne doit donc pas annoncer une économie exacte en octets à partir de ces seuls comptages logiques. La croissance asymptotique et la taille réelle sont deux mesures distinctes.

On peut réserver l'infini à l'absence d'arc et conserver zéro comme un poids valide. On peut aussi utiliser un indicateur de présence séparé du tableau de poids. Le choix doit être partagé par le constructeur, les algorithmes et l'affichage. Dans une matrice de distances, la diagonale zéro représente aussi le trajet vide ; elle ne doit pas être interprétée automatiquement comme une boucle physique. Une conversion correcte décrit donc sa convention, au lieu de traiter toutes les cases nulles comme absentes.

Avec la convention du cours, on place −1 sur la ligne B, +1 sur la ligne C et zéro sur les autres lignes. Les signes indiquent le départ et l'arrivée ; ils ne décrivent pas le coût. Le poids 1 se conserve séparément si le problème en a besoin. Dans une équation de conservation, les signes permettent de distinguer entrées et sorties. Mélanger poids et incidence ferait perdre cette interprétation, même si le poids vaut ici lui aussi 1.

C découvre E : son niveau vaut donc 2 et son parent est C. D possède lui aussi le niveau 2, mais E est déjà marqué lorsqu'on examine ses voisins. Le trajet passant ensuite de D vers E utiliserait une liaison supplémentaire et n'améliorerait pas le niveau. Le marquage dès l'ajout dans la file évite une nouvelle insertion. Le parent mémorise la première découverte, pas le voisin examiné en dernier.

La longueur est 3 arêtes et le coût vaut 4 + 5 + 6 = 15. BFS minimise la longueur, pas la somme de poids différents. Le trajet A–C–B–D–E–F coûte 13 mais comporte 5 arêtes ; il n'améliore donc pas l'objectif de BFS. Pour corriger une application qui voulait minimiser les dépenses, il faut changer l'algorithme choisi, et non modifier artificiellement les niveaux produits par le parcours en largeur.

Depuis C, DFS descend vers D, puis E, puis F. Les découvertes de D, E et F portent les dates 4, 5 et 6. Les fins se produisent ensuite dans l'ordre inverse : F à 7, E à 8, D à 9. C peut alors terminer à 10. Les appels imbriqués doivent finir avant celui qui les a ouverts. Ces dates comptent des événements de l'exécution ; elles ne mesurent pas une durée de traitement.

Les parents ont créé la branche A–B–C. L'arête CA revient vers l'ancêtre A encore actif et ferme le cycle A–B–C–A. L'examen de B depuis C correspond en revanche à l'arête BC qui vient de découvrir C. Dans un graphe simple non orienté, on ignore cette arête du parent pour ne pas annoncer un faux cycle. Avec des arêtes parallèles, il faut suivre l'identité de l'arête précise plutôt qu'ignorer indistinctement toutes les liaisons vers le parent.

A précède C et D ; B précède D ; C et D précèdent E ; E précède F. Chaque arc respecte donc l'ordre proposé. L'ordre n'est pas unique : A, B, C, D, E, F respecte aussi les contraintes. Les tâches sans relation imposée peuvent parfois permuter. Il faut vérifier les arcs plutôt que comparer la réponse à une liste unique. Si un cycle dirigé existe, aucune permutation ne peut satisfaire toutes les contraintes du cycle.

Non. Les racines dépendent de l'ordre des explorations et des possibilités d'atteinte. Elles ne regroupent pas les sommets qui peuvent se rejoindre dans les deux sens. Dans ce DAG, chaque sommet constitue sa propre composante fortement connexe : un retour entre sommets distincts créerait un cycle dirigé. Le graphe est pourtant relié si l'on oublie les flèches. Forêt DFS, connexité non orientée et forte connexité sont donc trois notions à distinguer.

Les propositions sont B à 2 + 1 = 3, D à 2 + 8 = 10 et E à 2 + 10 = 12. B avait déjà la valeur 4 depuis A ; il est amélioré. D et E étaient inconnus et deviennent accessibles. Les parents correspondants deviennent C. Ces valeurs restent provisoires : D descendra ensuite à 8, puis E à 10. Le tableau doit indiquer qu'il s'agit de l'état après les relaxations de C.

Depuis F, les parents conduisent à E, D, B, C puis A. En inversant la lecture, on obtient A–C–B–D–E–F. Le total vaut 2 + 1 + 5 + 2 + 3 = 13. Le tableau parent indique le prédécesseur sur le trajet depuis la source. Le lire directement depuis A ne donne pas une collection de successeurs ; un sommet pourrait d'ailleurs avoir plusieurs enfants. Il faut donc remonter depuis la destination choisie.

Après S, A vaut 2 et B vaut 5. Le minimum est A, qui est figé à 2. B est ensuite finalisé, mais son arc vers A ne peut plus corriger ce sommet dans la version classique. Pourtant S–B–A vaut 5 − 4 = 1. L'erreur est effective malgré l'absence de cycle. Une variante qui rouvre les sommets n'est plus la finalisation étudiée et ne bénéficie pas automatiquement de ses garanties.

T vaut successivement l'infini, 14, 9 et 6. Chaque passage lit exclusivement les distances du passage précédent. Le trajet optimal S–B–A–C–T utilise quatre arcs ; il devient donc disponible au quatrième passage. Une version en place pourrait propager certaines améliorations plus tôt selon l'ordre des arcs. Il ne faudrait alors plus interpréter chaque tableau comme les meilleurs trajets utilisant au plus le numéro du passage en arcs.

S possède la distance finie zéro. A et B appartiennent au circuit A–B–A de coût −2 ; leur coût peut diminuer sans limite en répétant ce circuit. T peut être atteint après ces répétitions et est donc affecté lui aussi. On marque A, B et T comme non bornés inférieurement, souvent avec le symbole −∞. Les dernières valeurs finies d'un tableau Bellman-Ford ne sont pas leurs minima. Le test supplémentaire sert précisément à empêcher cette fausse interprétation.

Le passage par B donne AC = AB + BC = 3 − 2 = 1. Le passage par C donne ensuite AD = AC + CD = 1 + 2 = 3, inférieur à l'arc direct de poids 10. Le chemin correspondant est A–B–C–D. Les deux étapes utilisent des ensembles d'intermédiaires progressivement autorisés. Elles ne signifient pas que la première étape autorise une seule arête et la suivante exactement deux.

BC utilise l'arc direct de poids −2. Pour aller de C vers B, on passe par C–D–B, de coût 2 + 4 = 6. Les poids et les sens ne sont pas symétriques. Le circuit B–C–D–B coûte 4, donc le répéter ne réduit pas les distances. Une matrice orientée asymétrique est parfaitement normale ; la rendre symétrique artificiellement changerait les déplacements autorisés et les solutions.

Avant AB, Kruskal a retenu BC, AC, DE et EF, de coût cumulé 8. A et B sont déjà dans la même composante, donc AB créerait un cycle et est refusée. BD réunit ensuite les composantes restantes. Les cinq arêtes retenues couvrent les six sommets et coûtent 13. Les arêtes plus lourdes n'ont plus besoin d'être examinées après cet arrêt. Un rejet ne signifie pas que le poids était trop grand en valeur absolue : il violait la structure de forêt.

Une installation minimale retient BC et AB pour un total de 3 ; BC et AC fournirait une autre solution de même coût. Pour préserver les distances depuis A, il faut les liaisons directes AB et AC, de coût global 4. Dans la première installation, A vers C vaut 3, au lieu de 2 dans le graphe complet. Minimiser la somme des arêtes et préserver les chemins depuis une source sont donc des objectifs distincts, même si les résultats coïncident parfois.

Non. Les parents de union-find décrivent seulement l'organisation des ensembles pour accélérer les recherches. Le lien vers la racine peut ne correspondre à aucune arête du graphe. Il faut conserver séparément la liste des arêtes acceptées par Kruskal. La compression conserve l'appartenance aux groupes ; elle ne modifie ni l'installation sélectionnée ni son coût. Mélanger ces deux structures produirait une solution graphique fausse malgré des tests de groupes corrects.

A reçoit 10 et envoie 4 + 6 = 10. B reçoit 5 + 4 = 9 et envoie 9. La conservation est respectée aux sommets intermédiaires. La source envoie 10 + 5 = 15, et le puits reçoit 6 + 9 = 15. Chaque valeur reste entre zéro et la capacité correspondante. Ces contrôles prouvent que la répartition est un flot admissible ; une coupe de même capacité ajoutera le certificat de maximalité.

Les capacités résiduelles directes sont 4 sur SA, 4 sur AB et 5 sur BT. Le goulot vaut donc 4. L'augmentation porte SA à 10, AB à 4 et BT à 9, tandis que SB reste à 5 et AT à 6. La valeur globale passe de 11 à 15. Il faut aussi ajouter les marges inverses correspondantes pour permettre une éventuelle annulation ultérieure ; oublier ces inverses rendrait la méthode générale incorrecte.

On utilise S–B–A–T. Le passage B–A annule le flot initial sur AB. Les augmentations sur SB et AT réorientent alors la répartition. Le résultat final possède une unité sur SA et AT, ainsi qu'une unité sur SB et BT ; AB revient à zéro. La valeur est 2. Le réseau résiduel décrit une modification de la solution provisoire, sans exiger un transport physique à rebours sur une conduite inexistante.

Pour {S}, les arcs sortants sont SA et SB, donc la capacité vaut 10 + 5 = 15. Pour {S, A}, les arcs allant vers l'autre côté sont SB, AB et AT, donc 5 + 4 + 6 = 15. Les deux coupes donnent la même borne. Le flot construit atteint 15 ; elles sont donc toutes deux minimales. Une coupe ne compte ni les arcs internes à son côté, ni les arcs entrant depuis l'autre côté.

Les relais minimaux se calculent par BFS, avec les niveaux et les parents comme trace. Les coûts minimaux du réseau principal se calculent par Dijkstra, car ses poids sont non négatifs ; Bellman-Ford fournit une vérification indépendante. L'installation se calcule par Kruskal ou Prim, dont les coûts doivent coïncider. Les sorties ne sont pas interchangeables. On vérifie les chemins et leurs sommes, puis la connexité, l'absence de cycle et le coût de l'arbre. Le stockage du graphe peut être partagé, mais chaque algorithme conserve son propre état.