3-02. Représentation des graphes
- Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs.
- Passer d’une représentation à une autre.
Dans ce chapitre, on s’intéresse à la structure des données représentant un graphe en programmation. Il en existe plusieurs possibles. Nous étudions ici les deux plus courantes : par matrice d’adjacence et par listes d’adjacences.
Dans tout ce chapitre, on considère un graphe $*G = \{S, A\}*$, orienté ou non, vérifiant les caractéristiques suivantes :
- $*S*$ contient $*n*$ sommets numérotés de 1 à $*n*$
- chaque sommet a au plus une boucle
- il existe au plus une connexion entre deux sommets.
Matrice d’adjacence
Cas des graphes non-valués
Une matrice d’adjacence est un tableau à deux dimensions de taille $*n \times n*$, où $*n*$ est le nombre de sommets du graphe. Chaque case $*M[i][j]*$ de la matrice indique s’il existe une arête entre le sommet $*i*$ et le sommet $*j*$. Pour un graphe non-valué, on utilise généralement :
- $*M[i][j] = 1*$ s’il existe une arête de $*i*$ vers $*j*$
- $*M[i][j] = 0*$ sinon
Dans le cas d’un graphe non orienté, la matrice est symétrique : $*M[i][j] = M[j][i]*$.
Exemple de matrice d’adjacence d’un graphe non-orienté
Matrice d’adjacence d’un graphe orienté
Donner la matrice d’adjacence pour le graphe ci-dessous.
Correction
Cas des graphes valués
Pour les graphes valués, la matrice d’adjacence fonctionne de la même manière, sauf qu’au lieu d’attribuer la valeur 1 à une connexion entre deux sommets, on lui attribue sa propre valeur. Si deux sommets ne sont pas connectés, la valeur de la « connexion » est conventionnelle. On peut lui attribuer la valeur 0, infinie (∞) ou encore NULL.
Matrice d’adjacence d’un graphe valué
Donner la matrice d’adjacence pour le graphe ci-dessous.
Correction
Avantages et inconvénients
La représentation d’un graphe à l’aide d’une matrice d’adjacence a de nombreux avantages :
- elle est facile à construire ;
- on a un accès rapide à une connexion donnée et aux voisins d’un sommet donné ;
- il est facile de connaître le nombre de chemin de longueur $*p*$ partant du sommet $*i*$ et arrivant au sommet $*j*$, par un théorème que je vous donnerai si on en a besoin plus tard.
Le principal inconvénient de la représentation d’un graphe par matrice d’adjacence est la taille mémoire puisqu’il faut gérer $*n^2*$ cases mémoires pour représenter un graphe à $*n*$ sommets.
Ce mode de représentation est en général utilisé uniquement pour les graphes de petite taille et les graphes denses, c’est-à-dire lorsque chaque sommet est connecté à la plupart des autres sommets, ou quand on veut savoir rapidement s’il existe une connexion entre deux sommets donnés.
Implémentation en Python
La solution la plus simple est bien sûr d’utiliser une liste de listes. Par exemple, l’implémentation du graphe 1a que l’on a vu plus haut sera :
M = [
[0, 1, 0, 1, 0],
[1, 0, 1, 0, 0],
[0, 1, 0, 1, 0],
[1, 0, 1, 0, 1],
[0, 0, 0, 1, 0]
]
Matrice d’adjacence en Python
1. Donner l’implémentation en liste de listes de la matrice d’adjacence pour le graphe ci-dessous.
2. Écrire un script qui donne l’ordre de ce graphe ?
3. Écrire un script qui donne la taille de ce graphe ?
4. Écrire une fonction qui permet de vérifier si un nœud $*i*$ est connecté à un nœud $*j*$ ?
Correction
1. Implémentation en Python
graphe = [
#a, b, c, e, f
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 0],
[0, 0, 0, 0, 1],
[1, 0, 0, 1, 0],
[1, 0, 0, 1, 0],
]
2. ordre du graphe
len(graphe)3. Taille du graphe
taille = 0
for sommet in graphe:
for connexion in sommet :
if connexion :
taille += 1
4. Existence d’une connexion entre deux sommets :
def are_connected(graphe, sommet1, sommet2) :
return bool(graphe[sommet1][sommet2])
Liste d’adjacence
Définition et exemples
Une liste d’adjacence est une autre structure de données utilisée pour représenter un graphe. Pour chaque sommet du graphe, on associe une liste contenant tous ses voisins, c’est-à-dire les sommets auxquels il est directement connecté.
Liste d’adjacence d’un graphe orienté
Donner la liste d’adjacence pour le graphe ci-dessous.
Correction
Avantages et inconvénients
La représentation des graphes à l’aide de listes d’adjacences a de nombreux avantages :
- elle est facile à construire ;
- elle permet de parcourir rapidement les voisins d’un sommet donné ;
- elle est compacte : on code uniquement les connexions présentes dans le graphe ;
- elle est robuste : on peut facilement modifier/ajouter des attributs pour prendre en charge les différents types de graphe.
Toutefois, elle a plusieurs inconvénients potentiels. Par exemple, pour déterminer si une connexion donnée $*p_{i,j}*$ est présent(e) dans le graphe, il n’existe pas de moyen plus rapide que de rechercher $*j*$ dans la liste d’adjacence du sommet $*i*$. Par conséquent, ce mode de représentation est en général utilisé pour les graphes peu denses, c’est-à-dire lorsque chaque sommet est connecté à un petit nombre d’autres sommets.
Implémentation
En Python, les listes d’adjacences d’un graphe peuvent être implémentées à l’aide d’un dictionnaire, les clés étant les sommets et les valeurs des listes, éventuellement vides, contenant les sommets adjacents associés à chacune des clés.
Adj = {
'a': ['b', 'e'],
'b': ['a', 'c'],
'c': ['b', 'e'],
'e': ['a', 'c', 'f'],
'f': ['e']
}
Liste d’adjacence en Python
1. Donner l’implémentation en dictionnaire de la liste d’adjacence pour le graphe ci-dessous.
2. Écrire un script pour déterminer l’ordre de ce graphe ?
3. Écrire un script pour déterminer la taille de ce graphe ?
4. Écrire une fonction qui vérifie si un nœud $*i*$ est connecté à un nœud $*j*$ ?
Correction
# question 1
graphe = {
"a" : ["b", "c"],
"b" : ["a", "c"],
"c" : ["f"],
"e" : ["a", "e"],
"f" : ["a", "e"],
}
# question 2
len(graphe)
# question 3
taille = 0
for sommets_adjacents in graphe.values():
taille += len(sommets_adjacents)
# question 4
def are_connected(graphe, sommet1, sommet2):
return sommet2 in graphe[sommet1]
Révision & entraînement
Représentations
Pour chacun des graphes ci-dessous, donner la représentation à l’aide d’une matrice d’adjacence et une représentation à l’aide de listes d’adjacences.
Correction
graphe1_matrice = [
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0],
]
graphe1_adjacences = {
1: [2],
2: [2, 4, 5],
3: [],
4: [1, 5],
5: [4],
6: [3],
}
graphe2_matrice = [
[0, 1, 1, 1, 1],
[1, 0, 1, 1, 0],
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 1],
[1, 0, 0, 1, 0],
]
graphe2_adjacences = {
1: [2, 3, 4, 5],
2: [1, 3, 4],
3: [1, 2],
4: [1, 2, 5],
5: [1, 4],
}
Matrice d’adjacence
On considère un graphe G dont la matrice d’adjacence est la matrice :
1. Le graphe $*G*$ est-il orienté ou non orienté ?
2. Quels sont l’ordre et la taille de $*G*$ ?
3. Donner une représentation du graphe $*G*$ sous forme de listes d’adjacences, puis sous forme graphique.
Correction
1. La matrice est symétrique, donc il s’agit d’un graphe non orienté.
2. Il s’agit d’une matrice 6×6, donc l’ordre du graphe est de 6.On compte 22 fois le nombre 1 dans la matrice. Mais comme il s’agit d’un graphe non orienté, chaque arête est comptée deux fois (une fois dans un sens, une fois dans l’autre). Il y a donc 11 arêtes.
3. Liste d’ajacence :
graphe = {
1: [2, 3, 4],
2: [1, 3, 5, 6],
3: [1, 2, 4, 5],
4: [1, 3, 5, 6],
5: [2, 3, 4, 6],
6: [2, 4, 5],
}
Liste d’adjacence
On considère un graphe G représenté par les listes d’adjacences suivantes :
1. Le graphe $*G*$ est-il orienté ou non orienté ?
2. Quels sont l’ordre et la taille de $*G*$ ?
3. Le sommet 2 peut-il être atteint à partir du sommet 1 ?
4. Donner une représentation du graphe $*G*$ sous la forme d’une matrice d’adjacence, puis sous forme graphique.
Correction
Graphes non orientés
Dans tout cet exercice, on considère un graphe simple non orienté.
Partie 1 – Matrice d’adjacence
On suppose dans cette partie que le graphe est représenté par sa matrice d'adjacence $*M*$ implémentée sous forme de liste de listes. On suppose également pour simplifier que les sommets du graphe sont les nombres entiers de 0 à $*n*$−1, où $*n*$ est le nombre de sommets du graphe.
1. La fonction get_liste_voisins ci-dessous prend en paramètre la matrice M et un sommet, et renvoie la liste des voisins de sommet. Compléter cette fonction.
def get_liste_voisins(M, sommet):
liste_voisins = []
for s in range(...):
if M[sommet][s] == ...:
liste_voisins.append(...)
return liste_voisins
2. Compléter la fonction sont_voisins ci-dessous qui prend en paramètre la matrice M et deux sommets du graphe, et renvoie un booléen.
def sont_voisins(M, sommet1, sommet2):
return ...
3. Compléter la fonction est_isole ci-dessous afin qu'elle réponde à sa documentation.
def est_isole(M, sommet):
'''
M = matrice d'adjacence d'un graphe simple non orienté
à n sommets numérotés de 0 à n-1
sommet = un sommet du graphe
Renvoie True si sommet est un sommet isolé, False sinon
'''
for s in range(...):
if M[...][...] != 0:
return ...
return ...
4. La fonction existe_chemin_longueur_2 ci-dessous prend en paramètre la matrice M et deux sommets du graphe, et renvoie un booléen. Compléter cette fonction.
def existe_chemin_longueur_2(M, sommet1, sommet2):
voisins_sommet1 = get_liste_voisins(...)
for sommet in voisins_sommet1:
if M[...][...] == 1:
return ...
return ...
5. Application. On considère le graphe suivant :
Implémenter la matrice d’adjacence et vérifier que les assertions ci-dessous ne provoquent aucune erreur.
# implémenter la matrice d’adjacence de ce graphe
M = ...
# Aucun des tests ci-dessous ne doit provoquer une AssertionError
assert get_liste_voisins(M, 4) == [1, 2, 3, 5]
assert sont_voisins(M, 1, 4)
assert not sont_voisins(M, 1, 5)
assert est_isole(M, 0)
assert not est_isole(M, 1)
assert existe_chemin_longueur_2(M, 1, 2)
assert not existe_chemin_longueur_2(M, 3, 6)
Partie 2 – Liste d’adjacence
On suppose à présent que le graphe est représenté par sa liste d'adjacence implémentées sous forme de dictionnaire, les clés étant les noms des sommets du graphe et les valeurs associées les sommets adjacents correspondants.
1. Réécrire les fonctions get_liste_voisins, sont_voisins, est_isole et existe_chemin_longueur_2 pour qu’elles utilisent une liste d’adjacence plutôt qu’une matrice d’adjacence.
2. Pour le graphe de la partie 1, écrire sa liste d’adjacence, puis exécuter les mêmes assertions pour tester vos fonctions.
Correction
Partie 1
def get_liste_voisins(M, sommet):
neighbor_list = []
for s in range(len(M)):
if M[sommet][s] == 1:
neighbor_list.append(s)
return neighbor_list
def sont_voisins(M, sommet1, sommet2):
return sommet2 in get_liste_voisins(M,sommet1)
def est_isole(M, sommet):
'''
M = matrice d'adjacence d'un graphe simple non orienté
à n sommets numérotés de 0 à n-1
sommet = un sommet du graphe
Renvoie True si sommet est un sommet isolé, False sinon
'''
for s in range(len(M)):
if M[sommet][s] != 0:
return False
return True
def existe_chemin_longueur_2(M, sommet1, sommet2):
voisins_sommet1 = get_liste_voisins(M, sommet1)
for sommet in voisins_sommet1:
if M[sommet2][sommet] == 1:
return True
return False
M = [
[ 0, 0, 0, 0, 0, 0, 0, 0 ], #0
[ 0, 0, 1, 0, 1, 0, 1, 1 ], #1
[ 0, 1, 0, 1, 1, 0, 0, 0 ], #2
[ 0, 0, 1, 0, 1, 0, 0, 0 ], #3
[ 0, 1, 1, 1, 0, 1, 0, 0 ], #4
[ 0, 0, 0, 0, 1, 0, 0, 1 ], #5
[ 0, 1, 0, 0, 0, 0, 0, 0 ], #6
[ 0, 1, 0, 0, 0, 1, 0, 0 ], #7
]
Graphes orientés
Dans tout cet exercice, on considère un graphe simple orienté.
Partie 1
On suppose dans cette partie que le graphe est représenté par sa matrice d'adjacence $*M*$ implémentée sous forme de liste de listes. On suppose également pour simplifier que les sommets du graphe sont les nombres entiers de 0 à $*n*$−1, où $*n*$ est le nombre de sommets du graphe.
1. La fonction successeurs ci-dessous prend en paramètre la matrice M et un sommet, et renvoie la liste des successeurs de ce sommet. Compléter cette fonction.
def get_successeurs(M, sommet):
liste_successeurs = []
for s in range(...):
if M[...][...] == 1:
liste_successeurs.append(...)
return liste_successeurs
2. Compléter la fonction prédécesseurs ci-dessous qui prend en paramètre la matrice M et un sommet, et renvoie la liste des prédécesseurs de sommet.
def get_predecesseurs(M, sommet):
liste_predecesseurs = []
for s in range(...):
if M[...][...] == 1:
liste_predecesseurs.append(...)
return liste_predecesseurs
3. Compléter la fonction est_isolé ci-dessous afin qu'elle réponde à sa documentation.
def est_isole(M, sommet):
'''
M est la matrice d'adjacence d'un graphe simple orienté
à n sommets numérotés de 0 à n-1
sommet est un sommet du graphe
Renvoie True si sommet est un sommet isolé du graphe, False sinon
'''
liste_predecesseurs = ...
liste_successeurs = ...
return ...
4. La fonction get_degres ci-dessous prend en paramètre la matrice M et un sommet, et renvoie un tuple contenant le degré entrant, le degré sortant et le degré du sommet. Compléter cette fonction.
def degres(M, sommet):
liste_predecesseurs = ...
liste_successeurs = ...
degre_entrant = ...
degre_sortant = ...
degre = ...
return degre_entrant, degre_sortant, degre
5. Applications. On considère le graphe suivant :
Implémenter la matrice d’adjacence et vérifier que les assertions ci-dessous ne provoquent aucune erreur.
# implémenter la matrice d’adjacence de ce graphe
M = ...
# Aucun des tests ci-dessous ne doit provoquer une AssertionError
assert get_successeurs(M, 1) == [2, 4, 6]
assert get_successeurs(M, 2) == []
assert get_predecesseurs(M, 1) == [4, 7]
assert get_predecesseurs(M, 2) == [1, 3, 4]
assert get_predecesseurs(M, 0) == []
assert est_isole(M, 0)
assert not est_isole(M, 5)
assert degres(M, 0) == (0, 0, 0)
assert degres(M, 1) == (2, 3, 5)
assert degres(M, 2) == (3, 0, 3)
assert degres(M, 6) == (1, 0, 1)
Partie 2
On suppose à présent que le graphe est représenté par ses listes d'adjacence implémentées sous forme de dictionnaire, les clés étant les noms des sommets du graphe et les valeurs associées les sommets adjacents correspondants.
1. Réécrire les quatre fonctions précédentes (get_successeurs, get_predecesseurs, est_isole, degres) de manière à ce qu’elles acceptent des listes d’adjacences plutôt qu’un matrice d’adjacences.
2. Implémenter les listes d'adjacence du graphe précédent, puis exécuter les mêmes assertions pour tester vos fonctions.
Correction
Partie 1
def get_successeurs(M, sommet):
liste_successeurs = []
for s in range(len(M)):
if M[sommet][s] == 1:
liste_successeurs.append(s)
return liste_successeurs
def get_predecesseurs(M, sommet):
liste_predecesseurs = []
for s in range(len(M)):
if M[s][sommet] == 1:
liste_predecesseurs.append(s)
return liste_predecesseurs
def est_isole(M, sommet):
liste_predecesseurs = get_predecesseurs(M, sommet)
liste_successeurs = get_successeurs(M, sommet)
return liste_predecesseurs == [] and liste_successeurs == []
def degres(M, sommet):
liste_predecesseurs = get_predecesseurs(M, sommet)
liste_successeurs = get_successeurs(M, sommet)
degre_entrant = len(liste_predecesseurs)
degre_sortant = len(liste_successeurs)
degre = degre_entrant + degre_sortant
return degre_entrant, degre_sortant, degre
M = [
[ 0, 0, 0, 0, 0, 0, 0, 0 ], #0
[ 0, 0, 1, 0, 1, 0, 1, 0 ], #1
[ 0, 0, 0, 0, 0, 0, 0, 0 ], #2
[ 0, 0, 1, 0, 1, 0, 0, 0 ], #3
[ 0, 1, 1, 1, 0, 1, 0, 0 ], #4
[ 0, 0, 0, 0, 0, 0, 0, 1 ], #5
[ 0, 0, 0, 0, 0, 0, 0, 0 ], #6
[ 0, 1, 0, 0, 0, 0, 0, 0 ], #7
]
Partie 2
def get_successeurs2(L, sommet):
return L[sommet]
def get_predecesseurs2(L, sommet):
liste_predecesseurs = []
for index, liste in enumerate(L):
if sommet in liste:
liste_predecesseurs.append(index)
return liste_predecesseurs
def est_isole2(L, sommet):
liste_predecesseurs = get_predecesseurs2(L, sommet)
liste_successeurs = get_successeurs2(L, sommet)
return liste_predecesseurs == [] and liste_successeurs == []
def degres2(L, sommet):
liste_predecesseurs = get_predecesseurs2(L, sommet)
liste_successeurs = get_successeurs2(L, sommet)
degre_entrant = len(liste_predecesseurs)
degre_sortant = len(liste_successeurs)
degre = degre_entrant + degre_sortant
return degre_entrant, degre_sortant, degre
# –––– Listes d’adjacences
L = [
[], #0
[2, 4, 6], #1
[], #2
[2, 4], #3
[1, 2, 3, 5], #4
[7], #5
[], #6
[1], #7
]