Aller au contenu principal

TP3 – Conversion et représentations des graphes

Objectifs
  • Comprendre qu’un même graphe peut avoir plusieurs représentations.
  • Savoir passer d’une liste d’adjacence à une matrice d’adjacence.
  • Exploiter une matrice d’adjacence pour analyser un graphe.
  • Consolider la manipulation des listes et des dictionnaires en Python.
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.

  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. 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.

  1. Implémenter la méthode correspondance_indices(self) qui retourne un dictionnaire : 
    {
        "A": 0,
        "B": 1,
        "C": 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.

  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. 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.

  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. Tester cette méthode sur un graphe orienté puis sur un graphe non orienté.

Pour aller plus loin​

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