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
Graphes orientés
Structure de données concrète
Selon 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
Un 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é |
|---|---|
| Modèle:Exemple | Modèle:Exemple |
Note pour l'exemple sur les graphes orientés :
- ligne = nœuds de départ
- colonne = nœuds d'arrivée
Listes d'adjacence
Un 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é |
|---|---|
| Modèle:Exemple | Modèle:Exemple |
Matrice d'incidence
Un 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é |
|---|---|
| Modèle:Exemple | Modèle:Exemple |
Listes d'incidence
Un 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é |
|---|---|
| Modèle:Exemple | Modèle:Exemple |
Opérations supportées
| 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.