L'objectif de ce TP est d'implémenter en Python un module de graphes.
Donnez une définition mathématique des graphes orientés.
En informatique, il existe plusieurs implémentations possibles des graphes orientés qui dépendent de la structure de donnée choisie pour coder la définition des graphes. On peut implémenter les graphes à l'aide de la liste d'adjacence, à l'aide de la matrice d'adjacence, ou à l'aide de la matrice d'incidence.
Rapellez le fonctionnement de chacune de ces trois structures de données.
Donner les listes d'adjacence, la matrice d'adjacence et la matrice d'incidence du graphe orienté de la Figure 1.
Reprendre l'exercice précédent pour les graphes non orientés.
Donner les listes d'adjacence, la matrice d'adjacence et la matrice d'incidence du graphe non orienté de la Figure 2.
Choisissez une structure de donnée et implémentez un module permettant de manipuler des graphes orientés et des graphes non orientés en Python.
Ce module contiendra un class OrientedGraph
et un class NonOrientedGraph
et doit permettre à l'utilisateur de pouvoir:
Ecrivez une fonction qui doit afficher graphiquement à l'écran un graphe.
Pour cela, vous allez utiliser Graphviz (voir www.graphviz.org
) qui est un outil de visualisation des graphes.
Pour ce faire, votre fonction
dotty
pour faire apparaître à l'écran le graphe présent dans le fichier précédement créé.
Voici un exemple de fichier au format DOT:
digraph G { 1 -> 2; 2 -> 3; 3 -> 1; }
Ce TP est inspiré du TP TD1 et des TD donnés au Licences Informatiques INF351 de l'Université Bordeaux 1.