Représentations des graphes
En algorithmique, un graphe abstrait \(G = (S, A)\) doit être représenté concrètement en mémoire afin de permettre son traitement par des algorithmes (parcours, Dijkstra, etc.).
Le choix de la représentation est crucial :
- il conditionne la complexité mémoire,
- et la complexité temporelle des opérations fondamentales (parcours, test d'adjacence, etc.).
On distingue principalement trois représentations classiques.
Liste d'adjacence
C'est la structure privilégiée pour les graphes dits "creux" (peu d'arêtes par rapport au nombre de sommets).
Principe
On associe à chaque sommet \(u \in S\) une liste contenant ses voisins. \[ Adj[u] = \{ v \in S \mid (u, v) \in A \} \]
Exemple
Graphe (a) - Non orienté
En observant le graphe, nous recensons les arêtes suivantes :
- \(A\) est relié à : \(B, D, E\)
- \(B\) est relié à : \(A, C, D, E\)
- \(C\) est relié à : \(B, D\)
- \(D\) est relié à : \(A, B, C\)
- \(E\) est relié à : \(A, B\)
adj_a = [
[1, 3, 4], # A est lié à B, D, E (index 0)
[0, 2, 3, 4], # B est lié à A, C, D, E (index 1)
[1, 3], # C est lié à B, D (index 2)
[0, 1, 2], # D est lié à A, B, C (index 3)
[0, 1] # E est lié à A, B (index 4)
]Graphe (b) - Orienté
En suivant les flèches :
- A : Les flèches partent vers B, D, E.
- B : Une seule flèche part vers E.
- C : Une seule flèche part vers B.
- D : Les flèches partent vers B, C.
- E : Aucune flèche ne part de E.
adj_b = [
[1, 3, 4], # A -> B, D, E
[4], # B -> E
[1], # C -> B
[1, 2], # D -> B, C
[] # E n'a pas de flèche sortante
]Utilisation de dictionnaire
L'utilisation d'un dictionnaire à la place d'une liste de listes est une variante très courante en Python, particulièrement utile lorsque les sommets ne sont pas numérotés de \(0\) à \(n-1\) (par exemple, si les sommets sont nommés "A", "B", etc.).
Au lieu d'utiliser l'indexation numérique d'un tableau, on utilise les identifiants des sommets comme clés du dictionnaire. Les valeurs associées sont les listes (ou ensembles) des voisins.
adj_a = {
"A": ["B", "D", "E"],
"B": ["A", "C", "D", "E"],
"C": ["B", "D"],
"D": ["A", "B", "C"],
"E": ["A", "B"]
}
adj_b = {
"A": ["B", "D", "E"],
"B": ["E"],
"C": ["B"],
"D": ["B", "C"],
"E": []
}Matrice d'adjacence
Représentation privilégiée pour les graphes denses ou pour les preuves utilisant l'algèbre linéaire.
Principe
On utilise une matrice carrée \(A\) de taille \(|S| \times |S|\) telle que : \[ A[u][v] = \begin{cases} 1 & \text{si } (u,v) \in A \\ 0 & \text{sinon} \end{cases} \]
Dans une matrice d'adjacence pondérée :
- l'entrée \(A[u][v]\) contient le poids de l'arête \(w(u,v)\),
- l'absence d'arête est représentée par :
- soit \(+\infty\),
- soit une valeur sentinelle (ex.
None), - jamais un poids valide.
Exemple
Pour les graphes précédents, on obtient les matrices suivantes :
Graphe (a) - Non orienté
A B C D E
A [0,1,0,1,1]
B [1,0,1,1,1]
C [0,1,0,1,0]
D [1,1,1,0,0]
E [1,1,0,0,0]Graphe (b) - Orienté
A B C D E
A [0,1,0,1,1]
B [0,0,0,0,1]
C [0,1,0,0,0]
D [0,1,1,0,0]
E [0,0,0,0,0]matrice_a = [
# A B C D E <- Sommet v
[0, 1, 0, 1, 1], # A
[1, 0, 1, 1, 1], # B
[0, 1, 0, 1, 0], # C
[1, 1, 1, 0, 0], # D
[1, 1, 0, 0, 0] # E
]
matrice_b = [
# A B C D E <- Sommet v
[0, 1, 0, 1, 1], # A
[0, 0, 0, 0, 1], # B
[0, 1, 0, 0, 0], # C
[0, 1, 1, 0, 0], # D
[0, 0, 0, 0, 0] # E
]Matrice d'incidence
La matrice d'incidence est une représentation algébrique d'un graphe.
Contrairement à la matrice d'adjacence (centrée sur les relations sommet–sommet), elle met en évidence les relations sommet–arête.
Principe
Soit un graphe : \[ G = (S, A) \text{ avec } |S| = n,\ |A| = m \] La matrice d'incidence est une matrice : \[ M \in \mathbb{R}^{n \times m} \]
- chaque ligne \(\Longleftrightarrow\) un sommet
- chaque colonne \(\Longleftrightarrow\) une arête
Cas d'un graphe non orienté
Pour une arête \(e_k = \{u,v\}\) : \[ M[i][k] = \begin{cases} 1 & \text{si } i = u \text{ ou } i = v \\ 0 & \text{sinon} \end{cases} \]
Exemple pour le graphe (a)
e1 e2 e3 e4 e5 e6 e7
AB AD AE BC BD BE CD
A [1, 1, 1, 0, 0, 0, 0]
B [1, 0, 0, 1, 1, 1, 0]
C [0, 0, 0, 1, 0, 0, 1]
D [0, 1, 0, 0, 1, 0, 1]
E [0, 0, 1, 0, 0, 1, 0]inc_a = [
# e1 e2 e3 e4 e5 e6 e7
[1, 1, 1, 0, 0, 0, 0], # A
[1, 0, 0, 1, 1, 1, 0], # B
[0, 0, 0, 1, 0, 0, 1], # C
[0, 1, 0, 0, 1, 0, 1], # D
[0, 0, 1, 0, 0, 1, 0] # E
]Cas d'un graphe orienté
Pour une arête orientée \(e_k = (u \rightarrow v)\) : \[ M[i][k] = \begin{cases} -1 & \text{si } i = u \quad (\text{sommet de départ}) \\ +1 & \text{si } i = v \quad (\text{sommet d'arrivée}) \\ 0 & \text{sinon} \end{cases} \]
- exactement un \(-1\)
- exactement un \(+1\)
Exemple pour le graphe (b)
e1 e2 e3 e4 e5 e6 e7
A→B A→D A→E B→E C→B D→B D→C
A [-1,-1,-1, 0, 0, 0, 0]
B [ 1, 0, 0,-1, 1, 1, 0]
C [ 0, 0, 0, 0,-1, 0, 1]
D [ 0, 1, 0, 0, 0,-1,-1]
E [ 0, 0, 1, 1, 0, 0, 0]inc_b = [
# a1 a2 a3 a4 a5 a6 a7
[-1, -1, -1, 0, 0, 0, 0], # A
[ 1, 0, 0, -1, 1, 1, 0], # B
[ 0, 0, 0, 0, -1, 0, 1], # C
[ 0, 1, 0, 0, 0, -1, -1], # D
[ 0, 0, 1, 1, 0, 0, 0] # E
]Tableau comparatif des représentations
| Critère | Liste d'adjacence | Matrice d'adjacence | Matrice d'incidence |
|---|---|---|---|
| Mémoire | \(O(|S| + |A|)\) | \(O(|S|^2)\) | \(O(|S| \times |A|)\) |
| Test d'adjacence \((u,v)\) | \(O(\deg(u))\) | \(O(1)\) | \(O(|A|)\) |
| Parcours des voisins de \(u\) | \(O(\deg(u))\) | \(O(|S|)\) | \(O(|A|)\) |
| Ajout d'une arête | \(O(1)\) | \(O(1)\) | \(O(1)\) (ajout de colonne) |
| Suppression d'une arête | \(O(\deg(u))\) | \(O(1)\) | \(O(1)\) (suppression de colonne) |
| Type de graphe idéal | Graphes creux | Graphes denses | Applications algébriques |
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.