Les graphes

Le modèle mathématique que nous allons étudier dans ce chapitre se nomme le graphe.

Un graphe est une structure de données constituée d'objets, nommés sommets et de relations entre ces sommets.

On peut classer les graphes en 2 catégories :


Vocabulaire

L'ordre d'un graphe est le nombre de ses sommets.

Vocabulaire des graphes non-orientés

Vocabulaire des graphes orientés


Multigraphes

Un graphe est dit simple si au plus une relation relie deux sommets et qu'il n'y a pas de boucle sur un sommet.

Sinon le graphe est dit multigraphe.

Exemple de multigraphe (non orienté)


Graphes étiquetés et pondérés

On appelle graphe étiqueté un graphe où chaque relation est affectée d'un symbole.

Dans le cas où les étiquettes sont un nombre positif, le graphe est appelé un graphe pondéré.

Ce type de graphe peut représenter par exemple une carte routière ou les pondérations correspondent à une distance en km ...

Un algorithme efficace pour déterminer le chemin le plus court d'un graphe pondéré pour aller d'un sommet donné à un autre est celui de Dijkstra.


Listes d'adjacence

Listes des successeurs et prédécesseurs associées à un graphe orienté

On peut représenter un graphe orienté en donnant la liste des successeurs, c'est à dire la liste des sommets que l'on peut atteindre directement par un arc à partir d'un sommet donné. On peut également la liste des sommets menant à un sommet donné : il s'agit alors de la liste des prédécesseurs.

Construire les listes des successeurs et des prédécesseurs de tous les sommets du graphe orienté suivant :

Sommet
Listes des successeurs
Listes des prédécesseurs
A
(B)
(C,D,F)
B
(C,D)
(A,D)
C
(A,D)
(B)
D
(A,B,E)
(B,C)
E
(D)
F
A
Listes des voisins associées à un graphe non-orienté

Dans un graphe non-orienté, le vocabulaire utilisé est celui des voisins d'un sommet.

Construire les listes des voisins de tous les sommets du graphe non-orienté suivant :

Sommet
Listes des voisins
A
(B,C,D,F)
B
(A,C,D)
C
(A,B,D)
D
(A,B,C,E)
E
(D,F)
F
(A,E)

Matrice d'adjacence associée à un graphe

On appelle matrice d'adjacence d'un graphe non étiqueté à n sommets notés $S_1, S_2, ..., S_n$, la matrice carrée (c'est à dire un tableau à n lignes et n colonnes) constituée des coefficients $a_{ij}$ tels que :

$ a_{ij} = \left\{ \begin{array}{ll} k \qquad \textbf{s'il existe k relations entre } S_i \textbf{ et } S_j \\ 0 \qquad \textbf{sinon}. \end{array} \right. $

Donner la matrice d'adjacence associée au graphe suivant :

$ A = \begin{pmatrix} 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix} $
Cette matrice s'obtient en remplissant un tableau où chaque ligne correspond au sommet de départ et chaque colonne au sommet d'arrivée.
1
2
3
4
5
A
B
C
D
E
1
A
0
1
1
0
1
2
B
0
1
1
1
1
3
C
0
0
0
1
0
4
D
1
0
0
0
0
5
E
0
0
1
0
0

La case rose correspond à $a_{34}$ à l'arc C -> D.

Donner la matrice d'adjacence du multigraphe :
$ \begin{pmatrix} 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 2 \\ 0 & 1 & 0 & 0\\ 0 & 2 & 0 & 0 \end{pmatrix} $

Remarque : la matrice d'adjacence d'un graphe non-orienté est symétrique.


Type abstrait graphe orienté

On définit les conventions suivantes :

Voici les opérations possibles sur le type abstrait Graphe à partir des données qui sont les sommets de type S.

Exemple d'application du type abstrait Graphe

Voici une liste d'instructions :

G = CREER_GRAPHE_VIDE()
AJOUTER_SOMMET(G,1)
AJOUTER_SOMMET(G,2)
AJOUTER_SOMMET(G,3)
AJOUTER_SOMMET(G,4)
AJOUTER_SOMMET(G,5)
AJOUTER_ARC(G,1,2)
AJOUTER_ARC(G,1,3)
AJOUTER_ARC(G,1,4)
AJOUTER_ARC(G,2,3)
AJOUTER_ARC(G,2,5)
AJOUTER_ARC(G,3,4)
AJOUTER_ARC(G,4,5)
AJOUTER_ARC(G,5,5)
AJOUTER_ARC(G,5,1)
			

Représenter graphiquement le graphe ainsi défini.