I. Représentation des graphes¶

Cours¶

Nous avons défini dans une séquence précédente la notion de graphe et son vocabulaire associé. Pour les utiliser informatiquement, il va falloir en donner une représentation mathématique que nous implémenterons ensuite.

A. Matrice d’adjacence¶

A.1. Graphes non-pondérés¶

Définition

On appelle matrice d’adjacence associée à un graphe \(G\) non-pondéré la matrice \(A\) dont le terme \(a_{ij}\) vaut 1 si les sommets \(i\) (indice de la ligne de la matrice) et \(j\) (indice de la colonne de la matrice) et sont reliés par une arête et \(0\) sinon, avec \(i\) et \(j\) variant de \(1\) à \(n\).

Exemple 1

Compléter la matrice d’adjacence de l’exemple ci-dessous.

graph LR
A((0)) --- B((1))
A --- C((2))
B --- D((3))
B --- E((4))
C --- G((5))
C --- E
E --- G

Solution

\(A = \begin{matrix} 0 & 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 1 & 0\\ \end{matrix}\)

Propriété
La matrice d’adjacence d’un graphe non-orienté est forcément symétrique par rapport à sa diagonale.

Exemple 2

Comparer la matrice d’adjacence précédente à celle du graphe ci-contre.

graph LR
A((0)) --> B((1))
A --> C((2))
B --> D((3))
B --> E((4))
C --> G((5))
C --> E
E --> G

Solution

\(A = \begin{matrix} 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0\\ \end{matrix}\)

A.2. Graphes pondérés¶

Définition

La matrice d’adjacence d’un graphe \(G\) pondéré est la matrice \(A\) dont le terme \(a_{ij}\) tel que :
- \(a_{ij}\) est le poids de l’arête (ou de l’arc) du sommet \(i\) au sommet \(j\),
- \(a_{ij} = 0\) si aucune arête (ou arc) ne relie les sommets \(i\) et \(j\).

Exemple 3

Compléter la matrice d’adjacence de l’exemple ci-contre.

graph LR
A((0)) --2--- B((1))
A --5--- C((2))
B --1--- D((3))
B --6--- E((4))
C --3--- G((5))
C --2--- E
E --8--- G

Solution

\(A = \begin{matrix} 0 & 2 & 5 & 0 & 0 & 0\\ 2 & 0 & 0 & 1 & 6 & 0\\ 5 & 0 & 0 & 0 & 2 & 3\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 6 & 2 & 0 & 0 & 8\\ 0 & 0 & 3 & 0 & 8 & 0\\ \end{matrix}\)

B. Listes d’adjacence¶

On peut également représenter un graphe avec, pour chacun de ses sommets, la liste des sommets auxquels il est relié.

Quelle différence cela fait-il par rapport à l’utilisation d’une matrice ?

On stocke moins de données car on ne représente que les connexions existantes (pas de "0").

Vocabulaire

Lorsque le graphe est non-orienté, on parle de liste de voisins. Lorsqu’il est orienté, en fonction des problèmes considérés, on choisit de le représenter par la liste de ses successeurs ou celle de ses prédécesseurs.

Exemples

Quelle est la liste des voisins représentant le graphe de l'exemple 1 ?

0: 1,2 / 1: 0, 3, 4 / 2: 0, 4, 5 / 3: 1 / 4: 1, 2, 5 / 5: 2, 4

Quelle est la liste des prédécesseurs de l'exemple 2 ? Sa liste des successeurs ?

liste des prédecesseurs : 0: aucun / 1: 0 / 2: 0 / 3: 1 / 4: 1, 2 / 5: 2,4 /
liste des successeurs : 0: 1, 2 / 1: 3, 4 / 2: 4, 5 / 3: aucun / 4: 5 / 5: aucun

TP : Représenter les graphes informatiquement¶

A. Implémentation avec une matrice d’adjacence¶

On considère le graphe représentant le réseau social ci-contre :

Donner sa matrice d’adjacence.

N.B. : lorsque les sommets sont étiquetés avec des lettres, on associe généralement le premier sommet dans l’ordre lexicographique (ici A) à la première ligne de la matrice, et ainsi de suite.

Pour la représenter en Python, nous allons utiliser une liste de liste Python (liste à deux dimensions).
Si on la stocke dans une variable m, on accède à l’élément de la ligne i et de la colonne j avec l’instruction m[i][j].

a. Représenter cette variable m pour notre exemple.

b. Quelle instruction permet de savoir si B et D sont adjacents ? A et E ?

Nous allons en fait utiliser une classe pour représenter notre graphe, de manière à pouvoir rajouter des méthodes nous donnant des propriétés sur le graphe :

class GrapheM:
    def __init__(self, matrice):
        self.m = matrice

    def est_adjacent(self, i, j):
        return ...

    def est_symetrique(self):
        for i in range(len(self.m)):
            for j in range(len(self.m[0])):
                if ...
                    return False
        return True

La méthode est_adjacent détermine si deux sommets i et j du graphe sont adjacents ou non.
a. Comment faut-il la compléter pour qu’elle fonctionne pour un graphe non-pondéré ?

b. Comment faut-il la compléter pour qu’elle fonctionne pour un graphe pondéré ? Utiliser cette deuxième version.
La méthode est_symetrique renvoie si, oui ou non, le graphe représenté par la matrice m est symétrique. Compléter-la.
Utiliser la matrice crée dans la question 2 pour créer un objet de la classe GrapheM représentant le graphe de l’exemple.

6. a. Quelle instruction permet de savoir si B et G sont adjacents ? A et H ?

<br>

b. Quelle instruction permet de savoir si le graphe de notre exemple est symétrique ?

<br><br>

B. Implémentation avec une liste d’adjacence¶

On considère un ensemble de site Web reliés par des liens hypertextes.

Donner sa représentation sous forme de matrice d’adjacence.

Donner sa représentation sous la forme de :
a. liste des prédécesseurs :

b. liste des successeurs :
Nous allons également utiliser une liste de liste Python pour représenter ce graphe sous forme de liste d’adjacence. Donner l’implémentation de la liste des successeurs de cet exemple :

Pour, cette fois aussi, associer des méthodes à notre représentation, nous utilisons une classe GrapheL :

class GrapheL:
    def __init__(self, lst):
        self.lst = lst

    def est_adjacent(self, i, j):
        return ...

    def graphe_vers_matrice(self):
        n = len(self.lst)
        mat = []
        for i in range(n):
            lst = [0 for i in range(n)]
            for x in self.lst[i]:
                lst[x] = 1
            mat.append(lst)
        return mat

On utilise la liste des successeurs. Compléter la fonction est_adjacent.
Représenter le graphe de l’exemple des sites Web avec un objet de la classe GrapheL en utilisant sa liste des successeurs.

6. a. Quelle instruction permet de savoir si les pages 3 et 4 sont adjacentes ?

<br>

b. Lire et analyser la fonction `graphe_vers_matrice`. Vérifier, à l’aide d’un appel de cette fonction, que l’on    obtient bien la matrice trouvée dans la question 1.

Si le nom de nos pages avait été, par exemple : Page 1 : NSI
2 : POO
3 : Récursivité
4 : Diviser_pour_régner 5 : Programmation_dynamique
6 : Calculabilité
quelle autre structure qu’une liste Python aurait-il été plus pertinent d’utiliser pour représenter le graphe ? Utiliser cette structure pour représenter l’ensemble des pages Web.

TD : Exercices sur la représentation des graphes¶

Exercice 1 :¶

Établir la matrice d’adjacence du graphe ci-dessous.

    graph LR
    A --- C
    D --- B
    A --- B
    A --- D

Établir sa liste d’adjacence (liste des voisins).

Exercice 2 :¶

On donne la matrice d’adjacence suivante :

\(\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{matrix}\)

Que peut-on dire sur les propriétés de ce graphe ?

Représenter le graphe correspondant.

Exercice 3 : connexité¶

Un graphe non-orienté est dit connexe si tous ses sommets peuvent être reliés deux à deux par une chaîne.

Donner un exemple de graphe non-connexe.

Un graphe orienté est dit fortement connexe si tous ses sommets peuvent être reliés deux à deux par un chemin.

Le graphe des pages Web utilisé en cours/TP est-il fortement connexe ?
Donner un (autre ?) exemple de graphe orienté fortement connexe.

Exercice 4 : passer d’une représentation à l’autre¶

On utilise la classe GrapheM définie en TP.

Écrire une méthode de la classe matrice_vers_liste qui permet de passer de la représentation par matrice d’adjacence à la représentation par liste d’adjacence : elle prend en entrée un objet de la classe GrapheM (le self) et renvoie cette liste d’adjacence représentée par une liste Python à deux dimensions.

N.B. : pour initialiser une liste Python vide à deux dimensions, penser à utiliser la compréhension.

On veut effectuer la même opération, mais stocker la liste d’adjacence dans un dictionnaire dont les clés sont les numéros des sommets et les valeurs contiennent la liste des sommets adjacents. Écrire la méthode matrice_vers_dictionnaire correspondante, prenant en entrée un objet de la classe GrapheM (le self) et renvoyant sa liste d’adjacence représentée avec un dictionnaire.