TD-8, graphes

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/X.97/TD-8/enonce.html

Programmes Prenom.Nom.c à déposer par ftp sur poly en /users/profs/maranget/TD-8.

1  Lecture et sauvegarde d'un graphe

Les exercices de cette semaine se feront à l'aide de la représentation des graphes par leur matrice d'adjacence. Or, il est bien plus commode pour un être humain de donner un graphe en spécifiant la liste des successeurs de chaque sommet.

On vous demande donc d'écrire un programme qui lit un graphe sous la forme de listes de successeurs et le sauve sous forme d'une matrice d'adjacence dans un fichier de nom graphe.

Donc, considérons un graphe pris au hasard, par exemple :





On le rentrera par une procédure à peu près similaire à celle-ci :
nombre de sommets : 5
1 : 3 4 2 0
2 : 0
3 : 4 5 0
4 : 2 5 0
5 : 2 0
À la fin de l'exécution du programme, le contenu du fichier graphe ressemblera à ceci :
5
0 1 1 1 0 
0 0 0 0 0 
0 0 0 1 1 
0 1 0 0 1 
0 1 0 0 0
Voici quelques points de programmation pour vous aider. Une solution apparaîtra en tab.txt.

2  Tri topologique

Le tri topologique d'un graphe produit la liste des sommets d'un graphe dans un ordre tel qu'un sommet est affiché avant tous ceux qui peuvent être atteints à partir de lui. Par exemple dans le cas du graphe déjà dessiné, un tri topologique possible est :
1 3 4 5 2
Pour nous fixer un peu les idées, supposons que ce graphe représente les contraintes sur certaines tâches, c'est à dire que, par exemple, la tâche numéro 3 doit être effectuée avant les tâches 4 et 5, mais après la tâche 1. Alors, le tri topologique fournit un ordonancement des tâches qui est compatible avec leurs dépendances.

Votre programme lira le graphe contenu dans le fichier de nom graphe et effectuera un tri topologique de ce graphe. Plus précisément : Pour tester un peu plus votre programme, voici un autre graphe à 21 sommets. Ce graphe représente les dépendances entre les chapitres d'un célebrissime ouvrage d'informatique fondamentale (cf. le poly, page 181).





Au lieu de rentrer vous-même ce graphe, vous pouvez utiliser le fichier graphe.txt. Voici un tri topologique inverse possible pour ce graphe :
12 13 20 21 17 16 15 19 10 9 8 7 6 14 11 18 1 5 4 3 2 
Note : votre programme, s'il ressemble à la solution, sera en O(n2). Il existe un tri topologique en O(n), mais il faut alors utiliser la représentation des graphes par listes de successeurs.

3  Composantes fortement connexes

Considérons un graphe cette fois cyclique :





En raison du cycle entre les sommets 3, 4 et 5, il n'est plus possible d'effectuer le tri topologique.

On définit ensuite la relation de connexité forte entre les sommets d'un graphe G: deux sommets i et j sont fortements connexes s'ils sont égaux ou s'il existe un chemin de i vers j et un chemin de j vers i. Cette relation est naturellement une relation d'équivalence et on appelle ``composantes fortements connexes'' ses classes d'équivalences. Les composantes fortement connexes sont en quelque sorte les cycles du graphe.

Les composantes fortement connexes de G peuvent être calculées relativement facilement à partir de la fermeture transitive G* du graphe G. En effet et par définition, deux sommets de G sont fortement connexes, si et seulement si il sont reliés par deux arcs réciproques de G*.

On demande donc d'écrire un programme qui : Dans le cas de notre graphe, on obtiendra :
1 
2 
3 4 5
Note : votre programme, s'il ressemble à la solution, sera en O(n3). Il existe un algorithme en O(n), mais il est réellement très astucieux.


Ce document a été traduit de LATEX par HEVEA.