Quelques algorithmes sur les graphes

Dans ce TD nous étudions une des structures fondamentales de l'informatique : les graphes. On commence
par détailler les diérentes manières de représenter un graphe en caml, et on les compare à travers quelques
algorithmes simples. Dans la troisième partie on étudie les algorithmes de parcours en profondeur et en largeur
d'un arbre, qui sont à la base de la plupart des algorithmes sur les graphes, fournissant une manière pratique de
parcourir tous les noeuds d'un graphe. Finalement, on s'intéressera à un algorithme de construction de circuits
eulériens dans un graphe. Cette dernière partie, plus dicile, est directement inspirée d'une partie du sujet d'info
ENS 2003.

1 Représentations

Dénition 1 (Graphe orienté). Un graphe orienté G est la donnée d'un couple (V , E ), où V est un ensemble
ni de sommets et E ⊂ V ×V une relation binaire sur V : l'ensemble des arêtes. Pour représenter graphiquement
un graphe, on dessine les sommets comme des cercles, et les arêtes comme des êches allant d'un sommet à un
autre.
Dénition 2 (Graphe non orienté). Un graphe non orienté est un un graphe pour lequel la relation binaire E
est symétrique et irréexive (symétrique pour qu'il n'y aie pas d'orientation et irréexive pour éviter les boucles
d'un sommet sur lui-même). On peut ainsi voir E comme un ensemble de paires plutôt que de couples.
Pour représenter un graphe il faut donc spécier à la fois son ensemble de sommets et son ensemble d'arêtes.
Comme on peut toujours se ramener à ce que l'ensemble des sommets soit l'ensemble {1, . . . , n}, où n = |V |, on
spéciera simplement le nombre de sommets par leur nombre n et l'on dénit
type sommet == int ; ;
La première représentation d'un graphe est par sa matrice d'adjacence. Si G = (V, E) est un graphe, on note
A la matrice de taille n × n à coecients dans {0, 1} dénie par Ai,j = 1 si (i, j) ∈ E et Ai,j = 0 sinon. La
matrice d'adjacence d'un graphe non orienté est donc une matrice symétrique. Le type correspondant est
type Agraph = {Ataille : int ; matadj : int vect vect} ; ;
Une deuxième façon de représenter un graphe est par l'ensemble de ses listes d'adjacence : à chaque sommet
i on associe la liste li = {j ∈ V, (i, j) ∈ E} ; le graphe est alors spécié par un vecteur contenant les listes
d'adjacence de chaque sommet.
type Lgraph = {Ltaille : int ; listeadj : sommet list vect} ; ;

2 Premiers algorithmes

Dénition 3 (taille). La taille d'un graphe G = (V, E) est t(G) = |V | + |E|. C'est le paramètre qui sert
habituellement à quantier la complexité d'un algorithme de graphes (bien qu'il soit parfois utile d'étudier la
complexité en fonction des deux paramètres n = |V | et m = |E|).
Question 1. Écrire des procédures Ltaille : Lgraphe -> int et Ataille : Agraphe -> int renvoyant la
taille d'un graphe donné dans chacune des deux représentations.
Dénition 4 (degré). Dans un graphe non orienté, le degré d'un sommet est le nombre d'arêtes qui lui sont
incidentes. Dans le cas d'un graphe orienté, on distingue le degré entrant (nombre d'arêtes qui arrivent à ce
sommet) du degré sortant (nombre d'arêtes qui en partent).

1
Question 2. Écrire des procédures {A,L}pred : {A,L}graphe -> sommet -> sommet list et
{A,L}succ : {A,L}graphe -> sommet -> sommet list qui, étant donné un graphe orienté (V , E ) et un som-
met i, renvoient respectivement la liste des sommets j tels que (i, j) ∈ E et celle des sommets j tels que (j, i) ∈ E .
Comparer leurs complexités.
Question 3. En déduire des procédures {A,L}degre : {A,L}graphe -> sommet -> int * int qui renvoient
le degré entrant et le degré sortant d'un sommet donné d'un graphe, dans les deux représentations. Donner la
complexité, en fonction de la taille du graphe et du degré du noeud considéré, de chacune de ces deux procédures
dans le pire cas. Quelle est leur complexité en moyenne ?
Question 4. Écrire des procédures {A,L}neigbour : {A,L}graphe -> sommet -> sommet -> bool telles que
{A,L}neighbour i j renvoie true si et seulement si (i, j) ∈ E . Comparer leurs complexités.
Dénition 5 (carré d'un graphe). Le carré d'un graphe orienté G = (V, E) est le graphe G2 = (V, E 2 ) tel que
(u, v) ∈ E 2 si et seulement s'il existe w ∈ V tel que (u, w) ∈ E et (w, v) ∈ E . C'est-à-dire qu'il y a une arête
dans le carré si, et seulement si, il y a un chemin de longueur exactement deux dans le graphe de départ.
Question 5. Écrire des procédures {A,L}carre : {A,L}graphe -> {A,L}graphe qui calculent le carré d'un
graphe. Comparer leurs complexités.
Comme vous avez pu le constater, chacune des deux représentations a ses avantages et ses inconvénients.
Un des inconvénients majeurs de la représentation par matrice d'adjacence est sa taille, qui est O(n2 ) quel que
soit le nombre d'arêtes de E , ce qui est beaucoup trop si le graphe est peu dense. Le plus gros inconvénient de
la représentation par liste d'adjacence est qu'il est relativement coûteux de tester si deux sommets donnés sont
reliés par une arête, ce que l'on a souvent besoin de faire en pratique.
On préférera souvent la représentation par listes d'adjacence si l'on est en train d'implémenter un algorithme
de complexité linéaire ou quasi-linéaire, alors que si l'on considère un algorithme à la complexité quadratique ou
plus, les diérences entres les deux représentations sont moins cruciales.

3 Parcours d'un graphe

On choisit dans cette section la représentation d'un graphe sous forme de liste d'adjacence. On va étudier
deux manières diérentes de parcourir l'ensemble des sommets d'un graphe. On verra ensuite des applications
algorithmiques de chacun de ces deux parcours.

3.1 Parcours en largeur

Le parcours en largeur d'un graphe permet un parcours du graphe en s'aidant d'une le contenant la liste
des noeuds à visiter, et construite au fur et à mesure. Il procède comme suit :
 Visiter le noeud de départ
 Retirer le premier noeud de la le, et le visiter
 Ajouter tous ses voisins non encore visités à la n de la le
 Si la le n'est pas vide retourner en 2

Question 6. Écrire une procédure largeur : Lgraphe -> sommet -> sommet list qui renvoie une liste conte-
nant l'ensemble des sommets du graphe, dans l'ordre d'un parcours en largeur commençant en un sommet passé
en argument. On poura utiliser la procédure @ de concaténation de deux listes. On pourra également s'aider d'un
vecteur auxiliaire pour marquer les sommets déjà visités.

3.2 Parcours en profondeur

Le parcours en profondeur d'un graphe permet un parcours de l'ensemble des sommets du graphe. Il s'aide
également d'une le contenant la liste des noeuds à visiter et procède comme suit :
 Visiter le noeud de départ
 Retirer le premier noeud de la le, et le visiter
 Ajouter tous ses voisins non encore visités au début de la le
 Si la le n'est pas vide retourner en 2

2
Question 7. Écrire une procédure profondeur : Lgraphe -> sommet -> sommet list qui renvoie une liste
contenant l'ensemble des sommets du graphe, dans l'ordre d'un parcours en profondeur commençant en un
sommet donné en argument. On poura utiliser la procédure @ de concaténation de deux listes.

3.3 Applications

Dénition 6. Soit G = (V, E) un graphe. Un chemin de G est une suite v1 , . . . , vp de sommets du graphe tels
que pour tout 1 ≤ i ≤ p − 1, (vi , vi+1 ) ∈ E . p est la longueur du chemin. Un cycle est un chemin tel que vp = v1 .
Question 8 (plus court chemin). Proposer un algorithme permettant de calculer la distance (i.e. la longueur du
plus court chemin) entre deux sommets dans un graphe. Le programmer et donner sa complexité.
Dénition 7. Un graphe orienté G est dit fortement connexe si, pour tous sommets v, v0 ∈ V de G, il existe
un chemin de v à v0 .
Question 9 (connexité). Déduire de l'algorithme du plus court chemin une procédure connexe : Lgraphe -> bool
permettant de tester si un graphe orienté g donné en entrée est fortement connexe. Quelle est sa complexité ?
On fera mieux à la question 16.
Question 10 (acyclicité). Proposer un algorithme permettant de tester si un graphe non orienté possède un
cycle. Le programmer et donner sa complexité.

4 Circuits Eulériens

Soit G = (V, E) un graphe et (i, j) ∈ E . Si π = v1 , . . . , vp est un chemin de G de longueur p, et e = (v, v 0 ) ∈ E

Dénition 8. Un cycle π de G est dit eulérien si et seulement si π passe par tout arc de G exactement une
fois, autrement dit si |π|e = 1 pour tout e ∈ E .
Question 11. Montrer que si G a un circuit eulérien, alors G vérie la loi de Kircho : tout sommet v de G a
son degré entrant et son degré sortant égaux.
Dénition 9. Un sommet isolé de G est un sommet de degré entrant et de degré sortant nuls.
Question 12. Montrer que si G a un circuit eulérien, et si G n'a pas de sommet isolé, alors G est fortement
connexe.
Question 13. On considère un chemin π tel que |π|e ≤ 1 pour tout arc e de G, et maximal avec cette propriéte.
Montrer que si G vérie la loi de Kircho, alors π est un circuit.
Question 14. Si de plus |π|e = 0 pour un arc e, et si G est fortement connexe, montrer qu'il existe un sommet
v par lequel passe π , et un circuit π 0 de v à v passant par e, et qui ne passe que par des arcs par lesquels π ne
passe pas.
En déduire que π est eulérien. Ainsi, un graphe fortement connexe vériant la loi de Kircho a un circuit
eulérien.
Question 15. Écrire une procédure euler qui prend en entrée un graphe g fortement connexe (dans une repré-
sentation de votre choix), et renvoie un circuit eulérien de g, sous la forme d'une liste de sommets décrivant le
circuit, s'il en a un, et la liste vide sinon.
Question 16. En déduire une procédure connexe permettant de teste si un graphe g est fortement connexe.
Quelle est sa complexité ? La comparer à celle de l'algorithme de la question 9.
De manière analogue aux circuits eulériens, on peut dénir les circuit hamiltoniens : un circuit de G est
hamiltonien s'il passe par chaque sommet exactement une fois. Malgré des dénitions semblables, ces deux
problèmes ne sont pas du tout de la même diculté : nous venons de voir que le problème de la recherche
d'un circuit eulérien pouvait être résolu en temps linéaire, alors que le problème de la recherche d'un circuit
hamiltonien est NP-complet (il est très lié au célèbre problème du voyageur de commerce). . .

3
4