Julien Sopena

TD 03 – Théorie des graphes : Algorithmes utilisant des parcours

Exercice 1: Composantes fortement connexes et tri topologique

Question 1.1 )

Appliquez l'algorithme du double parcours en profondeur pour trouver toutes les composantes fortement connexes du graphe Fig. 1. Dans cet algorithme, on utilisera l'ordre lexicographique dans les boucles (quand l'ordre n'est pas imposé par l'algorithme lui même).
Figure 1: Graphe à réduire

Question 1.2 )

On appelle graphe réduit GR d'un graphe G, le graphe tel que :
  • chaque sommet correspond à une composante fortement connexe de G
  • les arcs correspondent aux arcs de G dont les extrémités n'appartiennent pas à la même composante fortement connexe.

Tracez le graphe réduit du graphe de la Fig. 1.

Question 1.3 )

Montrez que le graphe réduit GR d'un graphe G quelconque ne peut pas contenir de circuit.

Question 1.4 )

Un graphe réduit peut-il être vu comme un graphe de précédence ?

Interprétez au niveau événementiel la signification des composantes fortement connexes du graphe G.

Question 1.5 )

Quelle est la matrice d'adjacence du graphe réduit ?

Question 1.6 )

Quelle est la matrice d'incidence du graphe réduit ?

Question 1.7 )

A l'aide d'une de ces représentations matricielles, donnez un ordre des événements du graphe réduit qui respecte la précédence et si possible l'ordre lexicographique.

Retrouvez ce résultat grâce à un parcours en profondeur.

Question 1.8 )

Retrouvez exactement ce résultat grâce à un parcours en profondeur.

Designed by OWSD.org. Valid CSS & XHTML
Ce site et l'ensemble de son contenu est mis à disposition sous un contrat Creative Commons.
Creative Commons License