Théorie des graphes/Fondements
Pour étudier les graphes et leurs utilisations, nous allons nous doter de définitions formelles, lister les représentations mémoire possibles et nous doter d’un modèle de graphe comme structure de données abstraite.
Graphes non orientés
modifier
Un graphe non-orienté est défini par un couple (S,A) où
- S est un ensemble de sommets
Notation : les sommets seront nommés u et v en général
Note : les sommets sont généralement étiquetés pour pouvoir les identifier
- A est un ensemble d’arêtes (u,v) liant deux sommets
Notation : les arêtes seront nommées a en général
Note : l’arête (u,v) = l’arête (v,u) ; les arêtes sont parfois étiquetées
Représentation graphique :
- Les sommets sont des ronds étiquetés
- Les arêtes sont des traits reliant les sommets
Soit le graphe G=(S, A) :
({1,2,3,4}, {(1,2), (2,3), (2,4), (4,2), (3,3)})
Graphes orientés
modifier Un graphe orienté est défini par un couple (N, A) où
- N est un ensemble de nœuds
Notation : les nœuds seront nommés n en général
- A est un ensemble d’arcs u→v liant un sommet de départ u à un sommet d'arrivée v (arcs)
Notation : les arcs seront nommés a en général
Représentation graphique :
- Les nœuds sont des ronds étiquetés
- Les arcs sont des flèches partant du nœud de départ et aboutissant à celui d’arrivée
Soit le graphe G=(N, A) :
({1,2,3,4}, {1→2, 2→3, 2→4, 4→2, 3→3})
Structure de données concrète
modifierSelon les définitions précédentes, un graphe peut se représenter comme un couple d'ensembles : on pourrait simplement stocker deux ensembles. Cependant, cela entraîne un problème d'efficacité :
- L'accès aux arêtes (ou arcs) incidents à un sommet (ou nœud) demande une recherche
- L'accès aux sommets (ou nœuds) adjacents à un sommet (ou nœud) demande une recherche
Dans un graphe, ce sont les relations d'incidence et d'adjacence qui sont importantes : on va utiliser des structures de données concrètes qui les intègrent.
Matrice d'adjacence
modifierUn graphe G=(S,A) à |S|=n sommets est représenté par une matrice M de booléens de taille n*n où :
- Les indices des lignes et des colonnes représentent des sommets
- M[i, j] = vrai si et seulement si l'arête (i, j) ∈ A
Notes :
- Occupation mémoire : O(n²)
- Pour les graphes orientés, on oriente la matrice
- Ne permet pas de représenter tous les graphes : les arêtes multiples ne peuvent être représentées
| Graphe non orienté | Graphe orienté |
|---|---|
|
Exemple
Soit le graphe G=(S, A) : ({1,2,3,4}, {(1,2), (2,3), (2,4), (3,3)})
|
Exemple
Soit le graphe G=(N, A) : ({1,2,3,4}, {1→2, 2→3, 2→4, 4→2, 3→3})
|
Note pour l'exemple sur les graphes orientés :
- ligne = nœuds de départ
- colonne = nœuds d'arrivée
Listes d'adjacence
modifierUn graphe G=(S, A) où |S|=n et |A|=m est représenté par une table T (ou une liste dont l'élément a deux champs suivant) de taille n où :
- chaque case représente un sommet et pointe sur un autre sommet (premier champ suivant)
- chaque case T[i] pointe sur la liste des sommets adjacents à i (deuxième champ suivant)
- la liste T[i] (deuxième champ suivant) est vide si i est isolé
Note :
- Occupation mémoire : O(n+m)
- Pour les graphes orientés, on ne liste que les arcs sortants (voir exemple ci-dessous)
- Permet de représenter tous les graphes
| Graphe non orienté | Graphe orienté |
|---|---|
|
Exemple
Soit le graphe G=(S, A) : ({1,2,3,4}, {(1,2), (2,3), (2,4), (3,3)})
|
Exemple
Soit le graphe G=(N, A) : ({1,2,3,4}, {1→2, 2→3, 2→4, 4→2, 3→3})
|
Matrice d'incidence
modifierUn graphe G=(S, A) où |S|=n et |A|=m est représenté par une matrice M de booléens de taille n*m où :
- les indices des lignes représentent des sommets
- les indices des colonnes représentent des arêtes
- M[i, j] = vrai si et seulement si l'arête j lie le sommet i
Notes :
- Occupation mémoire : O(n*m)
- Pour les graphes orientés, on utilise trois valeurs au lieu de booléens (départ, arrivée, et boucle)
| Graphe non orienté | Graphe orienté |
|---|---|
|
Exemple
Soit le graphe G=(S, A) : ({1,2,3,4}, {(1,2), (2,3), (2,4), (3,3)})
|
Exemple
Soit le graphe G=(N, A) : ({1,2,3,4}, {1→2, 2→3, 2→4, 4→2, 3→3})
|
Listes d'incidence
modifierUn graphe G=(S, A) où |S|=n et |A|=m est représenté par une table T (ou une liste) de taille n où :
- chaque case T[i] pointe sur la liste des arêtes incidentes à i
- la liste T[i] est vide si i est isolé
Notes :
- Occupation mémoire : O(n+m)
- Pour les graphes orientés, on ne liste que les arcs sortants
| Graphe non orienté | Graphe orienté |
|---|---|
|
Exemple
Soit le graphe G=(S, A) : ({1,2,3,4}, {(1,2), (2,3), (2,4), (3,3)})
|
Exemple
Soit le graphe G=(N, A) : ({1,2,3,4}, {1→2, 2→3, 2→4, 4→2, 3→3})
|
Opérations supportées
modifier| Type d'opération | Matrice d'adjacence | Liste d'adjacence | Matrice d'incidence | Liste d'incidence |
|---|---|---|---|---|
| Créer un graphe vide | O(1)* | O(1) | O(1)* | O(1) |
| Supprimer | O(1) | O(n+m) | O(1) | O(n+m) |
| Ajouter un sommet / nœud | O(1)* | O(1) | O(1)* | O(1) |
| Supprimer un sommet / nœud | O(1)* | O(m) | O(1)* | O(m) |
| Ajouter une arête / un arc | O(1)* | O(1) | O(1)* | O(1) |
| Supprimer une arête / un arc | O(1)* | O(1) | O(1)* | O(1) |
| Lister les voisins / successeurs d'un sommet / nœud | O(n) | O(1) | O(m) | O(m) |
| Lister les prédécesseurs d'un nœud | O(n) | O(m) | O(n*m) | O(n) |
| Lister les arêtes / arcs issus d'un sommet / nœud | O(n) | O(n) | O(m) | O(m) |
| Lister les arcs entrant en un nœud | O(n) | O(m) | O(n*m) | O(n) |
| Nombre de sommets / nœuds / arêtes / arcs | O(1) | O(1) | O(1) | O(1) |
* si les tableaux sont statiques, ils sont supposés préalloués à une taille suffisante. Si les tableaux sont dynamiques, il faut ajouter le coût de la réallocation.
