II.1 : Définition du
graphe
Un graphe G est un couple (X,A) où :
X : ensemble de sommets (noeuds ou points).
A : ensemble d'arêtes.
La figure 2.1 illustre bien ces notions :
A
B
E
D
C
X = {A,B,C,D,E}
A = {AB,AD,BD,BE,ED,DC}
Fig. 2.1 - Exemple
d'un graphe.
Remarque : l'arête est représentée
par ses deux extrémités, par exemple l'arête entre le
sommet A et le sommet B est représenté par AB.
II.2 : Le graphe
orienté (dirigé) ou digraphe
Un graphe orienté est un graphe dont ses arêtes
sont orientées. Voir la figure 2.2.
A
B
E
D
C
Fig. 2.2 - Exemple d'un graphe orienté.
Remarque : dans le cas des graphes orientés on
utilise le terme d'arc au lieu d'arête.
II.3 : Le graphe
étiqueté
Un graphe étiqueté est un graphe dont pour
chaque arête (ou arc) on associe une valeur. Voir la figure 2.3.
A
B
E
D
C
2
3
1
1
-1
-4
Fig. 2.3 - Exemple d'un graphe orienté
étiqueté.
II.4 : Notion de
chemin et de circuit (cycle orienté)
a) Le chemin
Un chemin est une séquence finie et alternée
de sommets et d'arcs, débutant et finissant par des sommets. On peut
extraire le chemin de la figure 2.4 à partir du graphe de la figure de
la figure 2.2.
A
B
D
Fig. 2.4 - Exemple de chemin.
Si aucun des sommets composants la séquence n'existe
plus d'une fois, alors le chemin est dit « chemin
élémentaire ». La figure 2.4 représente un
chemin élémentaire.
Si aucun des arcs composants la séquence n'existe plus
d'une fois, alors le chemin est dit « chemin simple ». La
figure 2.4 représente un chemin simple.
4.2 : Le circuit (cycle orienté)
Un circuit est un chemin dont les extrémités
coïncident.
Un circuit élémentaire ne contient pas le
même sommet plus d'une fois. La figure 2.5 représente un circuit
élémentaire.
B
E
D
Fig. 2.5 - Exemple d'un circuit élémentaire.
II.5 : La matrice
d'adjacence
Soit le graphe orienté G = (X,A) avec |X| = n
(l'ensemble X contient n sommets). La matrice d'adjacence du graphe G est la
matrice M de dimension nxn où
On prend comme exemple le graphe de la figure 2.2, sa matrice
d'adjacence est :
|
A
|
B
|
C
|
D
|
E
|
|
A
|
0
|
1
|
0
|
1
|
0
|
|
B
|
0
|
0
|
0
|
1
|
0
|
|
C
|
0
|
0
|
0
|
0
|
0
|
|
D
|
0
|
0
|
1
|
0
|
1
|
|
E
|
0
|
1
|
0
|
0
|
0
|
Fig. 2.6 - Exemple de matrice d'adjacence.
Pour les graphes étiquetés
On prend comme exemple le graphe de la figure 2.3, sa matrice
d'adjacence est :
|
A
|
B
|
C
|
D
|
E
|
|
A
|
0
|
2
|
0
|
3
|
0
|
|
B
|
0
|
0
|
0
|
-1
|
0
|
|
C
|
0
|
0
|
0
|
0
|
0
|
|
D
|
0
|
0
|
1
|
0
|
-4
|
|
E
|
0
|
1
|
0
|
0
|
0
|
Fig. 2.7 - Exemple de matrice d'adjacence d'un graphe
étiqueté.
Comme résumé pour ce chapitre, un graphe est un
ensemble de sommets liés par des arêtes (arcs), un graphe
orienté est un graphe avec des arêtes dirigées et un graphe
étiqueté est un graphe où les arêtes (arcs) ont des
valeurs. En plus de ça, on a vu la notion de chemin et de cycle
orienté et en fin on a vu la matrice d'adjacence qui est une autre
représentation du graphe (il faut noter que toutes les opérations
formelles sur les graphes sont basées sur la matrice d'adjacence).
| 
