L'objectif de ce TP est de compléter le module de graphe en ajoutant un algorithme de tri topologique, et de calcul des composantes fortements connexes.
Rapeller ce qu'est le tri topologique d'un graphe.
Appliquer l'algorithme de tri topologique basé sur l'algorithme PP au graphe ci-dessous en suivant l'ordre lexicographique:
Implémenter l'algorithme de tri topologique basé sur l'algorithme PP
.
Rappel:
PP(G) pour chaque sommet u de X faire couleur[u] <- BLANC pere[u] <- nil temps <- 0 pour chaque sommet u de X faire si couleur[u] = BLANC alors Visiter_PP(u)
Visiter_PP(u) couleur[u] <- GRIS d[u] <- temps <- temps + 1 pour chaque v de Adj[u] faire si couleur[v] = BLANC alors pere[v] <- u Visiter_PP(v) couleur[u] <- NOIR f[u] <- temps <- temps + 1
Rapeller ce qu'est une composante fortement connexe.
Appliquer l'algorithme de calcul des composantes fortement connexes au graphe ci-dessous:
Rappel:
Composantes_fortement_connexes(G): D <- PP(G). I <- inverse( D ). F <- PP( I ) en considerant les sommets dans l'ordre decroissant des f(u) de D Afficher les arborescences de la foret de F
Implémenter l'algorithme de calcul des composantes fortement connexes.
Soit un graphe de sommets et d'arêtes . Le graphe réduit est le graphe dont les sommets sont les composantes fortement connexes du graphe et les arêtes, les paires de sommets telles qu'il existe un arête du graphe vérifiant que est un sommet de la composante fortement connexe et est un sommet de la composante fortement connexe .
Déterminer le graphe réduit du graphe de l'exercice 1 et de l'exercice 2.
Donner un algorithme permettant de calculer le graphe réduit d'un graphe.
Implémenter cet algorithme.
Ce TP est inspiré du TP et des TDs donnés au Licences Informatiques INF351 de l'Université Bordeaux 1.