Théorie des graphes/Fondements
 |
|||
| Chapitre no1 | |||
| Leçon : Théorie des graphes | |||
|---|---|---|---|
| Retour au | sommaire | ||
| Chap. suiv. : | Propriétés | ||
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des graphes : Fondements
Théorie des graphes/Fondements », n'a pu être restituée correctement ci-dessus.
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.
Sommaire |
[modifier] Graphes non orientés
Définition
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
Définition
Représentation graphique :
- Les sommets sont des ronds étiquetés
- Les arêtes sont des traits reliant les sommets
Exemple
Soit le graphe G=(S, A) :
({1,2,3,4}, {(1,2), (2,3), (2,4), (4,2), (3,3)})
[modifier] Graphes orientés
Définition
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
Définition
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
Exemple
Soit le graphe G=(N, A) :
({1,2,3,4}, {1→2, 2→3, 2→4, 4→2, 3→3})
[modifier] 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.
[modifier] 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é |
|---|---|
|
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 :
- colonne = nœuds de départ
- ligne = nœuds d'arrivée
[modifier] Listes d'adjacence
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 sommets adjacents à i
- la liste T[i] 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})
|
[modifier] 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 3 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})
|
[modifier] 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é |
|---|---|
|
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})
|
[modifier] 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.
