Présentation et intérêt des graphes
En général, quand on doit résoudre un problème, celui-ci comporte tout un tas de détails inutiles que l’on abstrait en formalisant le problème. Un problème correctement formalisé est plus simple à résoudre, car on peut utiliser des outils classiques, en faisant abstraction du cas d’utilisation. Par exemple, trouver la route la plus courte d’une ville à une autre revient à résoudre un problème classique en théorie des graphes (que nous étudierons en détails plus loin dans le cours).
Mais commençons par le début : qu’est-ce qu’un graphe ? Informellement, la façon la plus simple de se rendre compte de ce qu’est un graphe est d’imaginer une carte routière. Chaque ville est un sommet dans le graphe, chaque route reliant deux villes est une arête dans le graphe, et on oublie le reste.
Le vocabulaire des graphes n’est pas standardisé, et cela peut parfois porter à confusion. Ce cours n’a pas vocation à insister sur les subtilités de nomenclature de la discipline. Mais il est important de savoir que selon les contextes un sommet peut devenir un nœud, une cellule, un neurone… De façon similaire, une arête est parfois une connexion, une synapse, un lien…
On obtient ainsi un couple composé de deux ensembles : des sommets, et des arêtes les reliant. On dit d’ailleurs que deux sommets reliés par une arête sont voisins.
L’intérêt de cette structure est son côté abstrait. Par exemple, prenez le graphe ci-dessous. Il peut représenter les villes et routes de Bretagne (les sommets sont les villes et les arêtes les routes), ou encore les relations professionnelles entre personnes… Ainsi, en s’intéressant à un problème défini sur un graphe, on peut résoudre une grande quantité de problèmes plus concrets.
Un peu plus formellement
Nous avons vu jusqu’alors les graphes de manière informelle, comme une structure de données constituée de sommets et d’arêtes. Plus formellement, un graphe est défini comme un couple (V; E), avec :
- V : Ensemble fini de sommets. On note généralement N le cardinal de V, et on nomme N l’ordre du graphe.
- E : Ensemble de paires de sommets appelés “arêtes”. Le cardinal de E s’appelle la taille du graphe.
En pratique, on numérotte les sommets, de sorte que de manière équivalente V = ⟦1; N⟧. Dans ce cas, on peut représenter E par la matrice d’adjacence W du graphe, définie comme suit :
- ∀ i, j ∊ ⟦1; N⟧ : Wi, j =
1 si {i; j} ∊ E;
0 sinon.
En conséquence, on peut définir un graphe par sa matrice d’adjacence W, avec la convention que la première ligne/colonne correspond au premier sommet, la seconde au second sommet, etc. Ainsi, si on reprend le graphe donné plus haut en exemple, et que l’on numérote ses sommets comme suit, on peut le décrire par la matrice d’adjacence suivante :
| 012345 |
|
Attention ! Un 0 dans la matrice indique que deux sommets ne sont pas voisins. Ceci est une convention, et il faut bien faire attention à ne pas penser que les sommets sont à une distance nulle (et donc infiniment proches).
Une définition importante : le chemin
Une fois que le problème est modélisé à l’aide d’un graphe, on a souvent envie de chercher la route la plus courte d’un sommet u à un sommet v par exemple. Pour cela, on définit la notion de chemin :
- Un chemin est une suite finie d’arêtes ({ui; ui+1})i telles que deux arêtes consécutives partagent exactement un sommet et tout arête apparaît au plus une fois dans le chemin.
- On appelle chemin élémentaire un chemin ne passant qu’une fois par chaque sommet du graphe.
- On appelle marche une suite (finie ou infinie) de sommets (ui)i telle que toute paire {ui; ui+1} est une arête. Sa longueur est son nombre d’éléments moins un.
- La longueur d’un chemin est son nombre d’arêtes.
- Enfin, un cycle est un chemin pour lequel la première et la dernière arête partagent un sommet. Un graphe sans cycle est dit acyclique.
En pratique, il n’existe pas toujours une (ou plusieurs) marches reliant deux sommets. Cela arrive notamment si on peut séparer les sommets du graphe en deux ensembles A et B tel qu’aucun sommet de A n’est relié par une marche à un sommet de B. On dit alors que le graphe n’est pas connexe.
Les graphes pondérés
Dans l’exemple précédent, chaque arête a la même importance. Si on veut se servir d’un tel graphe pour représenter des routes entre villes, on ne pourra pas modéliser le fait que certaines routes sont plus longues que d’autres. On introduit donc la notion de graphe pondéré, c’est à dire que l’on va associer des poids aux différentes arêtes. Pondérons donc le graphe précédent :
01234517311252
Comme dans cet exemple nous représentons des longueurs de routes, nous utilisons des entiers positifs (kilomètres). Toutefois, les pondérations utilisées dépendent de ce que l’on veut modéliser. Ainsi, pour des distances, on utilisera généralement des réels positifs, mais on pourrait tout aussi bien utiliser des valeurs négatives, des complexes ou des vecteurs selon le contexte.
Pour représenter un graphe pondéré, il suffit de remplacer les 1 dans la matrice d’adjacence (qui représentaient la présence d’une arête) par le poids associé. La matrice associée au graphe devient donc :
| 0 | 1 | 7 | 0 | 0 | 3 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 7 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 2 | 2 |
| 0 | 0 | 0 | 2 | 0 | 5 |
| 3 | 1 | 0 | 2 | 5 | 0 |
Lien avec le labyrinthe
Revenons au problème qui nous intéresse : on a un labyrinthe, dans lequel on aimerait ramasser des morceaux de fromage. Si on formalise un peu, on se rend compte que la notion de labyrinthe en elle même n’est pas très précise.
Ce qui nous intéresse plutôt est de savoir si on peut se rendre d’un point à un autre, et combien de mouvements sont nécessaires pour y arriver. Pour cela nous allons considérer un labyrinthe comme un graphe, dont les sommets sont les différentes cases du labyrinthe.
On ajoute ensuite les arêtes représentant les liens entre cases adjacentes. Les poids représentent le nombre de mouvements qu’il faut effectuer pour aller d’un sommet u à un sommet voisin v (donc dans le cas d’un labyrinthe sans boue, tous les poids valent 1 ou, de manière équivalente, le graphe n’est pas pondéré).
L’ensemble des informations utiles à la résolution du problème ayant été extrait, le problème est correctement formalisé. Il devient donc : “Soit un graphe pondéré G, un sommet de départ u0, et un ensemble de sommets T à visiter. Quelle est le plus court chemin partant de u0 passant par tous les sommets de T ?”.
Les graphes orientés
A présent, imaginons que nous voulions pouvoir indiquer dans notre modèle que certaines routes sont à sens unique. Il faut donc casser la symétrie du graphe pour indiquer que certaines routes ne sont pas à double sens. On introduit donc la notion de graphe orienté :
01234517311252
Dans l’exemple précédent, on peut aller du sommet 0 vers ses voisins (les sommets 1, 2 et 5), mais l’inverse n’est pas possible. On dit alors du sommet 0 que c’est un sommet source. Au contraire, on ne peut pas quitter le sommet 4 : on dit que c’est un sommet puits. Cela revient à considérer les arêtes comme des couples et non plus des paires de sommets.
Pour représenter un graphe orienté, il suffit de casser la symétrie dans la matrice d’adjacence. Ainsi, l’exemple précédent est représenté par la matrice suivante :
| 0 | 1 | 7 | 0 | 0 | 3 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 2 | 2 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 2 | 5 | 0 |
Enfin, passer à des graphes orientés implique des petits changement dans le vocabulaire :
- Une arête unidirectionnelle est appelée arc.
- Les voisins d’un sommet u accessibles en un mouvement (à partir de u) sont appelés les successeurs de u.
- Les voisins d’un sommet u pouvant accéder à u en un mouvement sont appelés les prédécesseurs de u.
Une alternative à la matrice d’adjacence
En général, le nombre d’arêtes dans un graphe est assez petit. Par exemple, dans le cas du labyrinthe, chaque sommet aura au plus quatre voisins. Ainsi, chaque ligne/colonne de sa matrice d’adjacence aura au plus quatre coordonnées non-nulles. Utiliser une matrice pour représenter la structure du graphe n’est donc pas forcément une bonne idée, car la plupart des coordonnées seront des 0, et prendront de la place pour rien.
Une solution classique est de ne représenter en mémoire que les arêtes existantes. Pour cela, on utilise en général un tableau de listes de la manière suivante :
- Le tableau comporte N cellules (la première correspond au premier sommet, la seconde au deuxième etc.).
- Chaque cellule du tableau contient une liste.
- Dans la liste de la i-ème case du tableau, on insère les sommets accessibles (successeurs) depuis le i-ème sommet, et les poids associés.
Reprenons le graphe pondéré et orienté précédent. Il peut être représenté par la structure suivante :
| 01234517311252 |
|
Dans cet exemple, le gain est assez minime étant donné que le graphe ne comporte que six sommets. Au lieu de stocker une matrice de 62 = 36 entiers, on stocke 11 paires d’entiers (soit 22 entiers).
Pour des graphes plus gros, la différence est bien plus conséquente. En effet, si on note N le nombre de sommets et M le nombre d’arêtes, une matrice contiendra N2 entiers, alors que cette structure plus adaptée en stockera seulement 2M. On pourra donc travailler sur de plus gros graphes.
Toutefois, utiliser cette structure a un prix, car tester l’existence d’une arête de u à v implique de parcourir toute la liste des successeurs de u, alors que l’information était immédiatement disponible avec la matrice d’adjacence en Wu, v.
Une autre solution
Dans le jeu PyRat, les programmes des joueurs reçoivent la carte du labyrinthe en début de partie. Cette carte (graphe du labyrinthe) est ensuite stockée de manière très légèrement différente. En effet, au lieu d’un tableau, on utilise une table de hachage. On accède donc à la liste des voisins d’un sommet u en utilisant la position de u (paire (x; y) des coordonnées de u, avec l’origine en bas à gauche) comme clé.
Pour approfondir
- La théorie des graphes appliquée à Pacman
- La théorie spectrale des graphes (complètement hors-champ mais super intéressant, et ce cours est très bien fait)