Les
Graphes…
Avant de donner une définition formelle de ce qu’est un graphe, nous commencerons par donner trois exemples de graphes :
Figure 1 : Exemple des graphes
Les cercles gris portent le nom de sommet et les lignes reliant les différents sommets se nomment arête. On remarque que le premier et les troisième graphe sont orientés (leurs arêtes possèdent une direction) alors que le second graphe est non-orienté. De plus, on voit que le troisième graphe est valué (les arêtes possèdent un coût).
DÉFINITION :
GRAPHE ORIENTÉ
Un graphe orienté G est une paire (S, A) où S est un ensemble fini de sommets et A est une relation binaire sur S et constitue l’ensemble des arêtes de G.
On peut donc exprimer le premier graphe de la figure 1 ainsi :
G = (S, A) = ({0, 1, 2, 3, 4, 5},
{(0, 0), (0, 1), (0, 2), (1, 3), (2, 1), (2, 3), (3, 2), (5, 4)}}
DÉFINITION :
GRAPHE NON-ORIENTÉ
Un graphe non-orienté G est une paire (S, A) où S est un ensemble fini de sommets et A est un ensemble de couple(s) non ordonné(s) de sommets. De plus, les boucle sont interdites dans les graphes non-orientés.
On peut donc exprimer le second graphe de la figure 1 ainsi :
G = (S, A) = ({0, 1, 2, 3, 4, 5},
{(0, 1), (0, 3), (1, 3), (4, 5)}}
où, par exemple, le couple (0, 1) serait
équivalent au couple (1, 0).
Le nombre
d’arêtes touchant un sommet se nomme degré. Le degré
entrant d’un sommet est le nombre d’arêtes dont ce sommet est la
destination, alors que le degré
sortant d’un sommet est le nombre d’arêtes dont ce sommet est la
source. Par exemple, dans le premier graphe de la figure 1, voici les
degrés des différents sommets :
|
Sommet |
Degré |
Degré entrant |
Degré sortant |
|
0 |
4 |
1 |
3 |
|
1 |
3 |
2 |
1 |
|
2 |
4 |
2 |
2 |
|
3 |
3 |
2 |
1 |
|
4 |
1 |
1 |
0 |
|
5 |
1 |
0 |
1 |
Comment conserver un graphe de façon statique ?
Il existe évidemment plusieurs façon de gérer un graphe
d’un point de vue informatique. La première façon que nous présenterons
consiste tout simplement à utiliser un tableau de taille n x n où
n constitue le nombre de sommets du graphe. Si le graphe n’est pas
valué, alors chaque case [i][j] du tableau contiendra une valeur booléenne (0
ou 1) indiquant l’absence ou la présence d’une arête entre les sommets i et j.
Si le graphe est valué, alors chaque case [i][j] du tableau contiendra le coût
de l’arête reliant les sommets i et j. Dans ce cas, la valeur ∞
représentera l’absence d’arête. Voici la représentation des trois graphes de la
figure 1 :
|
1 |
1 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
0 |
0 |
|
|
4 |
3 |
3 |
∞ |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
0 |
0 |
|
|
∞ |
5 |
∞ |
∞ |
|
0 |
1 |
0 |
1 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
∞ |
∞ |
1 |
2 |
|
0 |
0 |
1 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
|
|
∞ |
7 |
∞ |
6 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
|
|
0 |
0 |
0 |
0 |
1 |
0 |
|
|
|
|
|
|
Figure
2 : Représentation à l’aide de tableau des trois graphes de la figure 1
On remarque que si le graphe n’est pas orienté, la matrice correspondante est symétrique et ne contient que des 0 sur sa diagonale (voir le tableau du centre de la figure 2). On voit aussi que la somme des 1 dans une colonne donne le degré entrant d’un sommet alors que la somme des 1 dans une ligne donne son degré sortant.
AVANTAGES
Implantation facile à réaliser,
Accès rapide aux informations du graphe
(un seul accès en mémoire).
DÉSAVANTAGES
Nécessite une allocation contiguë en
mémoire ce qui peut limiter la taille du problème pouvant être résolu,
Conçu pour contenir un nombre fixe de
sommets.
Comment conserver un graphe de façon dynamique ?
Si le graphe est conservé de façon dynamique, alors cela signifie qu’au besoin les arêtes et les sommets seront ajoutés durant l’exécution de l’application. Pour ce faire, nous ferons une utilisation intensive des pointeurs. Voici une illustration de l’implantation suggérée :
Figure 3 : Représentation dynamiques de graphes
En plus d’un pointeur, les sommets peuvent contenir des informations supplémentaires. De la même façon, les arêtes peuvent contenir plus de données que simplement l’indice du sommet de destination.
EXEMPLE DE GRAPHE IMPLANTÉ EN C
(avec des tableaux dynamiques)
typedef struct
{
// Mettre ici les données concernant un
sommet.
} sommet
typedef struct
{
int depart;
// Sommet de depart de
l’arête.
int
destination; // Sommet d’arrivée de
l’arête.
double coût; // Dans le cas d’un graphe valué.
} arête
typedef struct
{
sommet *
sommets; // Les sommets du graphe.
int nb_sommets; // Nombre de sommets du graphe.
arête * arêtes;
// Les arêtes du graphe.
int nb_arêtes; // Nombre d'arêtes du graphe.
} graphe
AVANTAGES
Possibilité d’ajouter et de retirer des
sommets et des arêtes,
DÉSAVANTAGES
Recherche plus lente,
Utilisation supplémentaire de mémoire
pour conserver les pointeurs.
Quelques algorithmes très connus…
Voici plusieurs traitements que l’on pourrait vouloir effectuer sur un graphe accompagné d’un algorithme existant permettant de le réaliser.
Recherche,
à partir d’un sommet de départ, de tous les sommets atteignables et de leur
distance :
Breadth-first search (parcours en
largeur)
Recherche du chemin le plus court entre deux
sommets :
Algorithme de Dijkstra
Recherche du chemin le plus court entre tous
les sommets d’un graphe :
Algorithme de Floyd-Warshall
Trouver l’arbre de recouvrement minimal (un
minimum d’arêtes permettant de toucher à tous les sommets du graphe et dont la
somme des poids est minimal) :
Algorithme de Kruskal
Algorithme de Prim
Exemple :
Figure 4 : Exemple d’arbre de recouvrement minimal
Trouver
le flot maximal entre deux sommets d’un graphe valué et orienté :
Méthode
de Ford-Fulkerson
-
Cormen, leiserson & rivest, Introduction to Algorithms, McGraw Hill, 1028 pages.
-
labelle, Théorie des graphes, Modulo, 183 pages