TP 1 - première implémentation des graphes

L'objectif de ce TP est d'implémenter en Python un module de graphes.

Exercice 1

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.

Un  graphe orienté
Figure 1 - Un graphe orienté

Exercice 2

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.

Un graphe non orienté
Figure 2 - Un graphe non orienté

Exercice 3

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:

Exercice 4

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

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.