Aller au contenu principal

TP3 – Conversion et représentations des graphes

Pré-requis
  • Avoir réalisé les TP1 et TP2 sur les graphes.
  • Maîtriser la représentation par liste d’adjacence.
Documentation
  • Toutes les méthodes demandées seront ajoutées à la classe GrapheOriente.
  • Elles seront automatiquement disponibles pour GrapheNonOriente grâce à l’héritage.
  • Les sommets seront considérés dans l’ordre alphabétique.

Dans ce TP, nous allons travailler sur un changement de représentation des graphes.
Jusqu’à présent, les graphes étaient représentés par une liste d’adjacence.
Nous allons maintenant introduire une seconde représentation : la matrice d’adjacence.

Rappel : matrice d’adjacence​

Une matrice d’adjacence est un tableau à deux dimensions.

  • Les lignes correspondent aux sommets de départ ;
  • Les colonnes correspondent aux sommets d’arrivée ;
  • La valeur :
    • 1 indique l’existence d’un arc (ou d’une arête) ;
    • 0 indique son absence.

Exemple :

matrice = [
    [0, 1, 0],
    [0, 0, 1],
    [1, 0, 0]
]

Ici, le sommet 0 est relié au sommet 1, le sommet 1 au sommet 2, et le sommet 2 au sommet 0.

Conversion vers une matrice d’adjacence​

On souhaite maintenant écrire une méthode permettant de convertir le graphe (stocké en liste d’adjacence) en matrice d’adjacence.

ExercicesTout déplier
  1. 1
    Implémenter la méthode conversion_vers_matrice(self) qui :
    • retourne une matrice (liste de listes) ;
    • respecte l’ordre alphabétique des sommets ;
    • place 1 lorsqu’un arc existe, 0 sinon.
  2. 2
    Tester la méthode sur un graphe orienté puis sur un graphe non orienté.

Associer sommets et indices​

Dans une matrice, les sommets sont représentés par des indices numériques.
Il est donc nécessaire de connaître la correspondance entre les sommets et les indices de lignes / colonnes.

ExercicesTout déplier
  1. 1
    Implémenter la méthode correspondance_indices(self) qui retourne un dictionnaire : 
    {
        "A": 0,
        "B": 1,
        "C": 2,
        ...
    }
  2. 2
    Vérifier que cette correspondance est cohérente avec la matrice obtenue précédemment.

Degré à partir de la matrice​

On souhaite maintenant calculer le degré d’un sommet à partir de la matrice d’adjacence.

ExercicesTout déplier
  1. 1
    Implémenter la méthode degre_matrice(self, sommet) qui :
    • utilise la matrice d’adjacence ;
    • retourne le degré du sommet passé en paramètre.
  2. 2
    Comparer les résultats avec la méthode degre déjà implémentée précédemment.

Symétrie de la matrice​

Dans un graphe non orienté, la matrice d’adjacence est symétrique.

ExercicesTout déplier
  1. 1
    Écrire une méthode est_symetrique(self) qui :
    • retourne True si la matrice d’adjacence du graphe est symétrique ;
    • retourne False sinon.
  2. 2
    Tester cette méthode sur un graphe orienté puis sur un graphe non orienté.

Pour aller plus loin​

ExercicesTout déplier
  1. 1
    Écrire une méthode conversion_depuis_matrice(self, matrice, sommets) permettant de reconstruire un graphe à partir d’une matrice d’adjacence.
  2. 2
    Comparer les avantages et inconvénients des deux représentations :
    • liste d’adjacence ;
    • matrice d’adjacence.