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é

$µ \begin{array}{r|ccccc} & a & b & c & e & f \\ \hline a & 0 & 1 & 0 & 1 & 0 \\ b & 1 & 0 & 1 & 0 & 0 \\ c & 0 & 1 & 0 & 1 & 0 \\ e & 1 & 0 & 1 & 0 & 1 \\ f & 0 & 0 & 0 & 1 & 0 \end{array} µ$

Connexion entre sommets

$µ M = \begin{pmatrix} 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 \end{pmatrix} µ$

Matrice d’adjacence

Matrice d’adjacence d’un graphe orienté

Donner la matrice d’adjacence pour le graphe ci-dessous.

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.

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 donnerais 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]
		]

On peut également utiliser les arrays du module Numpy lorsqu’on a certains besoins calculatoires spécifiques ou que le graphe est de grande taille.

🖐️ N’oubliez cependant jamais un des principes de bases en développement, le principe KISS (Keep It Simple, Stupid). 😁
N’utilisez l’artillerie lourde que si vous en avez besoin.

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. Comment déterminer l’ordre de ce graphe ?

3. Comment déterminer la taille de ce graphe ?

4. Comment vérifier si un nœud $*i*$ est connecté à un nœud $*j*$ ?

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

$µ \begin{array}{r|ccccc} a & b & e \\ b & a & c \\ c & b & e \\ e & a & c & f \\ f & e \end{array} µ$

Liste d’adjacence

Liste d’adjacence d’un graphe orienté

Donner la liste d’adjacence pour le graphe ci-dessous.

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. Comment déterminer l’ordre de ce graphe ?

3. Comment déterminer la taille de ce graphe ?

4. Comment vérifier si un nœud $*i*$ est connecté à un nœud $*j*$ ?

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.

Matrice d’adjacence

On considère un graphe G dont la matrice d’adjacence est la matrice :

$µ M = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ \end{pmatrix} µ$

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.

Liste d’adjacence

On considère un graphe G représenté par les listes d’adjacences suivantes :

$µ \begin{array}{r|ccccc} 1 & 3 & 4 & 5 \\ 2 & 3 & 5 \\ 3 & 1 & 2 & 4 \\ 4 & 1 & 2 \\ 5 & 2 \end{array} µ$

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.

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

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
				]