T G
T G
T G
Khadra Bouanane
1
Table des matières
2
TABLE DES MATIÈRES 3
5 Arbres et arborescences 54
1 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2 Arborescence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Chapitre 1
Processus 1 2 3 4 5 6 7 8
Ressources R1,R3,R4 R4,R5 R2,R6 R1 R3,R6 R3 R1,R5 R6
On cherche alors à déterminer le nombre maximum de processus qu’on peut activer simultané-
ment ?
Pour répondre à cette question, il faut considérer les processus qui n’ont aucune ressource com-
mune. Afin de mieux visualiser nos données, on peut penser à utiliser un schéma ou graphe où on
représente les processus par des points et on relie deux points si les processus ont au moins une
ressource commune. nous obtenons donc le schéma ou graphe suivant :
Dans ce schéma, puisque deux point sont reliés indiquent que les processus représentés par ces
4
Chapitre 1. Notions de base de la Théorie des graphes 5
points ont au moins une ressource commune, on doit donc considérer le maximum de points qui ne
sont pas reliés. On peut alors facilement déduire que le nombre maximum de processus qu’on peut
activer en même temps est égal à 4, soit les processus 2,4,6,8 ou 2,4,6,3, comme le montre la figure
suivante :
Remarques 1.1 .
1. Dans le langage de la théorie des graphes, des points qui ne sont pas reliés sont appelés stable.
Donc, en utilisant un graphe comme modèle dans cet exemple, le problème revient à chercher
un stable maximum.
2. On aurait pu obtenir la solution directement à partir des données, car on a une petite instance,
mais le modèle graphe devient indispensable si on avait 50 ou 100 processus.
De manière générale, si on cherche à résoudre un problème concret, en utilisant les outils de la
théorie des graphes, on doit passer par les étapes suivantes :
Problème concret
⇓
Modèle Graphe adéquat
⇓
Identifier le problème (qu’est ce qu’on doit chercher dans le graphe)
⇓
Choisir un algorithme conçu pour le problème en question
⇓
Trouver la solution du problème concret
2 Définitions de base
Intuitivement
Un graphe est une représentation ou schématisation d’une situation concrète par des points et des
lignes ou des arcs reliant ces points et qui sert à mieux comprendre cette situation ; cette repré-
sentation peut être d’une carte géographique, d’un corps chimique où d’un réseau électrique ou de
télécommunication ou autre.
Mathématiquement
Un graphe, noté G = (V, E), est défini par deux ensembles disjoints notés V et E où
V = {v1 , v2 , · · · , vn } sont les sommets de G
E = {e1 , e2 , · · · , em } constitué de paires (non ordonnées) de V sont les arêtes de G.
La Théorie des graphes est le domaine mathématique et informatique qui étudie
– les propriétés théoriques des graphes,
– les algorithmes de graphes.
Exemple 2.1 .
Soit G le graphe représenté dans la Figure 1.1.
Incidence et adjacence.
– Un sommet u ∈ V est dit incident à l’arête e ∈ E, si u est une extrémité de e.
– Une arête e ∈ E est incidente à un sommet u s’il est une de ses extrémités.
– Deux sommets sont dits adjacents s’ils sont incidents à une même arête.
– Deux arêtes sont dites adjacentes si elle ont une extrémité en commun.
– L’ensemble de sommets adjacents au sommet u mais différents de u, est appelé ensemble de
voisins de u et est noté N (u).
Chapitre 1. Notions de base de la Théorie des graphes 8
Exemple 2.2 .
Dans le graphe représenté dans la Figure 1.1, on a :
– Les sommets 1 et 2 sont incidents à l’arête e1 .
– L’arête e3 est incidente au sommet 5.
– Les sommets 1 et 5 sont adjacents car il y a l’arête e4 qui les relie.
– Les arêtes e2 et e4 sont adjacentes car elle ont une extrémité en commun.
– L’ensemble de voisins du sommet 2, est N (2) = {1, 5}.
Nombre chromatique. On appelle k-coloration d’un graphe G = (V, E), une application
telle que pour toute paire de sommets adjacents u et v ont des couleurs différentes ( µ(u) 6= µ(v)).
On dit que G est k-colorable s’il admet une k-coloration.
Chapitre 1. Notions de base de la Théorie des graphes 9
Le nombre chromatique du graphe G, noté χ(G), est alors le plus petit entier k tel que G est
k-colorable.
Exemple 2.4 .
Le graphe de la figure 1.4, est 3-colorable donc k-colorable, pour 3 ≤ k ≤ 5. De plus c’est le nombre
chromatique car le graphe contient un triangle (clique de cardinalité 3).
Indice chromatique On appelle k-arête coloration d’un graphe G = (V, E), une application
π : E −→ {1, 2, ..., k}
F IGURE 1.5 – Il nous faut 4 couleurs pour colorier les arêtes de ce graphe.
Chapitre 1. Notions de base de la Théorie des graphes 10
F IGURE 1.6
1 2 3 4 5
1 0 1 1 0 1
2 1 1 0 0 1
3 1 0 0 2 0
4 0 0 2 0 1
5 1 1 0 1 0
Matrice d’incidence
Définition 2.2. G = (V, E) un graphe tel que |V | = n et |E| = m.
La matrice d’incidence B représente la relation d’incidence sommets-arêtes. Elle est de di-
mension n × m où chaque élément bij représente le nombre de fois qu’une arête ej est incidente au
sommet vi . On peut remarquer que la somme des éléments de chaque colonne de B est égal à 2.
Exemple 2.7 .
La matrice d’incidence du graphe de la Figure 1.6 est définie comme suit :
Chapitre 1. Notions de base de la Théorie des graphes 11
e1 e2 e3 e4 e5 e6 e7 e8
1 1 1 0 1 0 0 0 0
2 1 0 1 0 0 0 0 2
3 0 1 0 0 1 1 0 0
4 0 0 0 0 1 1 1 0
5 0 0 1 1 0 0 1 0
Proposition 2.1 .
Soit G = (V, E) un graphe d’ordre n et de taille m, tel que V = {v1 , v2 , . . . , vn }. On a
n
X
dG (vi ) = 2|E| = 2m.
i=1
Preuve.
On considère la matrice d’incidence B = [bij ] du graphe G = (V, E). Chaque ligne correspond à un
sommet vi et chaque colonne correspond à une arête ej .
On remarque que si on fait la somme de chaque ligne i, on obtient le degré du sommet vi . C’est
à dire : m
X
bij = d(vi ), 1 ≤ i ≤ n. (1.1)
j=1
D’autre part, On sait que la somme de chaque colonne est égale à 2. c’est à dire :
n
X
bij = 2, 1 ≤ j ≤ m. (1.2)
i=1
Chapitre 1. Notions de base de la Théorie des graphes 12
D’où on a n
X
d(vi ) = 2m = |E|.
i=1
Corollaire 2.1 .
Dans un graphe, le nombre de sommets de degré impair est pair.
3 Graphes particuliers
Et on a la propriété suivante :
Proposition 3.1 .
Pour un graphe simple G et son complémentaire Ḡ, on a
Exemple 3.1 .
Le complémentaire du graphe de la Figure 1.7 est représenté dans la Figure 1.8.
Chapitre 1. Notions de base de la Théorie des graphes 13
.
Exemple 3.2 .
Le graphe de la Figure 1.9 est 3-régulier :
4 Notion de sous-graphe
Soit G(V, E) un graphe et soient les sous ensembles W ⊂ V et F ⊂ E.
– On dit que H = (W, F ) est un sous-graphe de G si ∀e = uv ∈ F , les extrémités u, v sont
dans W .
– Lorsque F est formé de toutes les arêtes de E dont les extrémités sont dans W , alors le sous-
graphe H est appelé sous-graphe de G induit par W et est noté GW . Il est défini de manière
unique.
– Lorsque W contient uniquement les extrémités des arêtes de F , alors H est appelé sous-
graphe induit par F , noté G[F ]. Il est défini de manière unique.
– Lorsque W = V alors le sous-graphe H est appelé graphe partiel.
Exemple 4.1 .
Soit G le graphe suivant :
F IGURE 1.12
5 Graphes orientés
Définition 5.1. Un graphe orienté G = (V, A) est formé de deux ensembles disjoints ; l’ensemble
de sommets V = {v1 , v2 , . . . , vn } et l’ensemble A = {a1 , a2 , . . . , am }, qu’on appelle ensemble des
arcs de G tel que tout arc ai est une paire ordonnée d’éléments de V . A est défini par une relation
binaire de V dans V , qui n’est pas symétrique.
Exemple 5.1 .
Le graphe de la Figure 1.17 est un graphe orienté avec V = {1, 2, 3, 4, 5} et A = {a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 }.
Remarques et notations.
– Les relations d’incidence entre sommets et arcs et les relations d’adjacence entre sommets
ou entre arcs sont définies exactement de la même façon que celles pour les graphes non
orientés.
– Étant donné un arc a = uv, le sommet u est appelé extrémité initiale et est noté I(a), le
sommet v est appelé extrémité terminale et est noté T (a).
– Pour un sommet u ∈ V , on appelle successeur de u, tous les sommets v tels que uv est un
arc.
– Pour un sommet u ∈ V , on appelle prédécesseur de u, tous les sommets v tels que vu est un
arc.
– L’ensemble des successeurs (resp. l’ensemble des prédécesseurs) du sommet u est noté N + (u)
(resp. N − (u)) et l’ensemble de voisins de u, N (u) est tel que N (u) = N + (u) ∪ N − (u).
– Un graphe orienté est dit simple s’il est sans boucle, et que entre deux sommets, il existe au
plus un arc. Comme celui présenté dans la Figure 1.18.
– On dit que le graphe orienté G est complet si toute paire de sommets est relié par un seul arc.
C’est à dire ∀u, v ∈ V, uv ∈/ A ⇒ vu ∈ A ( voir Figure 1.19).
F IGURE 1.18 – Un graphe orienté simple F IGURE 1.19 – Un graphe orienté complet
1 2 3 4 5
1 0 1 1 0 0
2 0 1 0 0 1
3 0 0 0 1 0
4 0 0 1 0 0
5 1 0 0 1 0
Matrice d’incidence.
Définition 5.3. Soit G = (V, A) un graphe orienté sans boucles d’ordre n et de taille m avec V =
{v1 , v2 , . . . , vn } et A = {a1 , a2 , . . . , am }.
La matrice d’incidence de G, notée B = [bij ] est alors définie comme suit :
1 si le sommet vi est l’extrémité initiale de l’arc aj (I(aj ) = vi )
bij = −1 si le sommet vi est l’extrémité terminale de l’arc aj (T (aj ) = vi )
0 sinon
Exemple 5.3 .
La matrice d’incidence du graphe G ci-dessous est définie comme suit :
a1 a2 a3 a4 a5 a6 a7
1 1 1 0 -1 0 0 0
2 -1 0 1 0 0 0 0
3 0 -1 0 0 1 -1 0
4 0 0 0 0 -1 1 -1
5 0 0 -1 1 0 0 1
5.2 Demi-degré
Soit G = (V, A) un graphe orienté et u ∈ V .
– Le demi-degré extérieur du sommet u, noté d+ G (u) est le nombre d’arcs ayant u comme
extrémité initiale.
– Le demi-degré intérieur de u, noté d− G (u), est le nombre d’arcs qui ont u comme extrémité
terminale.
−
– On a dG (u) = d+ G (u) + dG (u).
– Une source s du graphe G est un sommet de G tel que d− G (s) = 0.
Chapitre 1. Notions de base de la Théorie des graphes 18
F IGURE 1.21
−
– d+ G (2) = 1 et dG (2) = 3
– d− +
G (3) = 3 et c’est un puits car dG (3) = 0.
– Le sommet 5 est une source car d− G (5) = 0.
et on a la proposition suivante
Proposition 5.1 .
Dans tout graphe orienté G = (V, A) d’ordre n et de taille m, on a
X X
d+
G (u) = d−
G (u) = |A| = m.
u∈V u∈V
6 Représentation en machine
Un graphe peut être introduit sur machine de plusieurs manières différentes, on distingue la
représentation statique et la représentation dynamique :
Table des successeurs. Un graphe orienté G = (V, A) peut être représenté comme suit :
Pour chaque sommet vi , on énumère la liste de ses successeurs, ces listes sont rangées les unes
après les autres, dans l’ordre naturel des sommets qui lui sont associés, dans un tableau (vecteur)LS,
et un autre tableau d’ordre n qu’on note P S qui contient des pointeurs ou les indices pour repérer le
1er successeur de chaque sommet vi dans le tableau LS. L’absence de successeurs est codée par 0.
Chapitre 1. Notions de base de la Théorie des graphes 19
Exemple 6.1 .
La table des successeurs du graphe de la Figure 1.20, est construite comme suit :
1 2 3 4 5
1 3 4 5 6
2 3 5 4 3 1 4
F IGURE 1.22
Liste de successeurs De manière analogue, un graphe orienté G = (V, A) peut être représenté sur
machine par la liste des successeurs, définie par un tableau de dimension n, où chaque élément i
pointe vers la liste des successeurs du sommet vi .
Exemple 6.3 .
Soit le graphe suivant :
Chapitre 1. Notions de base de la Théorie des graphes 20
F IGURE 1.23
1 2 3 /
2 5 /
3 4 /
4 3 /
5 1 4 /
Chapitre 2
1 Définitions
1.1 Chaînes/Chemins
Chaîne.
On appelle chaîne, dans un graphe non orienté (resp. orienté) G = (V, E) resp.(G = (V, A)), une
séquence alternée de sommets et d’arêtes (resp. d’arcs)
σ = v1 e1 v2 e2 v3 . . . vk ek vk+1 (resp.σ = v1 a1 v2 a2 v3 . . . vk ak vk+1 )
tel que ∀1 ≤ i ≤ k, les sommets vi et vi+1 sont les extrémités de l’arête ei (resp. de l’arc ai ). On dit
que σ est une chaîne reliant les sommets v1 et vk+1 , de longueur k.
F IGURE 2.1 – σ = 3e2 1e1 2e8 2e3 5 est une chaîne F IGURE 2.2 – σ = 1a2 3a6 4a7 5a3 2 est une chaîne
de longueur 4 reliant les sommets 3 et 5. de longueur 4 reliant les sommets 1 et 2.
Chemin.
On appelle chemin, dans un graphe orienté G = (V, A), une séquence alternée de sommets et d’arcs
η = v1 a1 v2 a2 v3 . . . vk ak vk+1
tel que ∀1 ≤ i ≤ k, le sommet vi est l’extrémité initiale de l’arc ai et le sommet vi+1 est l’extrémité
21
Chapitre 2. Cheminements dans les graphes 22
F IGURE 2.3 – η = 1a1 2a3 5 est un chemin de longueur 2 du sommet 1 vers le sommet 5.
– Le chemin 1a1 2a8 2a3 5 est un chemin simple mais non élémentaire car il utilise le sommet 2,
deux fois.
– La chaîne 5a7 4a6 3a6 4a9 1 n’est ni simple ni élémentaire.
– La chaîne 3a2 1a4 5a7 4 est une chaîne élémentaire et simple.
Remarques 1.1 .
1. Un chemin (resp. chaîne) élémentaire est nécessairement simple mais la réciproque n’est pas
toujours vraie.
2. Si le graphe G est simple, on peut alors définir un chemin ou une chaîne comme une séquence
de sommets uniquement.
Chapitre 2. Cheminements dans les graphes 23
F IGURE 2.4 – σ = 1e1 2e8 2e3 5e4 1 est un cycle F IGURE 2.5 – σ = 1a2 3a6 4a7 5a4 1 est un cycle
dans G1 . dans G2 .
Circuit.
On appelle circuit dans un graphe orienté G = (V, A), un chemin simple η = v1 a1 v2 . . . vk ak vk+1 tel
que v1 = vk+1 .
F IGURE 2.6 – la séquence η = 5a7 4a9 1a1 2a3 5 constitue un circuit dans ce graphe.
Remarques 1.2 .
– Un cycle ou circuit est élémentaire, si les sommets qui le composent sont tous distincts (dif-
férents).
– Dans un graphe simple, un cycle ou un circuit peut être défini par énumération de la séquence
des sommets.
Chapitre 2. Cheminements dans les graphes 24
2 Connexité
R est une relation d’équivalence, car elle est réflexive, symétrique et transitive. Elle partitionne donc
l’ensemble de sommets V en plusieurs classes d’équivalence.
Les sous-graphes de G induits par les classes d’équivalence de cette relation sont appelés com-
posantes connexes de G.
Remarques 2.1 .
– Un graphe est connexe s’il possède une seule classe d’équivalence, sinon, il n’est pas connexe
et possède p composantes connexes.
– Un sommet isolé est une composante connexe du graphe.
Proposition 2.1 .
Un graphe G d’ordre n qui est connexe, possède au moins n − 1 arêtes ou arcs.
Proposition 2.2 .
Si on ajoute une arête à un graphe G, on a pour conséquence :
– soit de diminuer le nombre de composantes connexes de G,
– soit de créer un nouveau cycle dans G.
– L’ensemble des arêtes F = {12, 13, 14} est une coupe dans G, car la suppression de ces
arêtes déconnecte G.
– Son arête-connectivité λ(G) est égale à 3, donc G est 3 arête-connexe.
On a aussi le résultat suivant :
Proposition 2.3 .
Dans tout graphe G de degré minimum δ(G), dont la connectivité est κ(G) et l’arête connectivité
λ(G), on a
κ(G) ≤ λ(G) ≤ δ(G).
Chapitre 2. Cheminements dans les graphes 27
F IGURE 2.10 – Ce graphe est tel que δ(G) = F IGURE 2.11 – Dans ce graphe, κ(G) =
κ(G) = λ(G) = 3. 1, λ(G) = 2 et δ(G) = 3.
3 Forte connexité
Définition 3.1. Un graphe orienté G = (V, A) est dit fortement connexe, si pour chaque paire de
sommets u et v, il existe un chemin de u à v et un chemin de v à u.
Le graphe représenté dans la Figure 2.12 est fortement connexe.
F IGURE 2.12
R est une relation d’équivalence, car elle est réflexive, symétrique et transitive. Elle partitionne donc
l’ensemble de sommets V en plusieurs classes d’équivalence.
Chapitre 2. Cheminements dans les graphes 28
Les sous-graphes de G induits par les classes d’équivalence de cette relation sont appelés com-
posantes fortement connexes du graphe G.
Remarque 3.1 .
Pour un sommet u du graphe orienté G = (V, A), on définit
– L’ensemble des descendants du sommet u : D(u) = {v ∈ V, tel qu’il existe un chemin de u à v}.
– L’ensemble des ascendants du sommet u : A(u) = {v ∈ V, tel qu’il existe un chemin de v à u}.
– On peut alors écrire la relation R comme suit :
u=v
uRv ⇐⇒ ou
v ∈ D(u) ∩ A(u)
Donc la composante fortement connexe qui contient u, peut être déterminée par l’intersection de
ses descendants et de ses ascendants. Ceci constitue le principe de l’algorithme de recherche des
composantes fortement connexes dans un graphe orienté.
Exemple 3.1 .
Trouver les composantes fortement connexes du graphe de la Figure 2.13.
F IGURE 2.13
Exemple 3.2 .
Le graphe réduit du graphe de la Figure 2.14 est représenté par la Figure 2.15. Avec
– C1 = C(1) = {1, 2, 5},
– C2 = C(3) = {3, 4, 7},
– C3 = {6}.
4 Cheminements Eulériens
Définition 4.1. Soit G = (V, E) (resp. G = (V, A)) un graphe connexe.
– Un cheminement (cycle, chaîne, circuit, chemin) d’un graphe est dit Eulérien, s’il utilise
toutes les arêtes ou les arcs du graphe une et une seule fois.
– Un graphe est dit Eulérien s’il contient un cycle eulérien.
– Un graphe G est dit semi-Eulérien s’il contient une chaîne eulérienne.
Proposition 4.1 .
Un graphe G = (V, E) connexe est Eulérien si et seulement si tous les sommets ont un degré pair.
Autrement dit, ∀u ∈ V, dG (u) ≡ 0[2].
Proposition 4.2 .
Un graphe G = (V, E) connexe est semi-Eulérien si et seulement s’il existe exactement deux sommets
de degré impair. Autrement dit, ∃a, b ∈ V tels que dG (a) ≡ dG (b) ≡ 1[2], et ∀u 6= a, b ∈ V, dG (u) ≡
0[2].
Proposition 4.3 .
Soit G = (V, A) un graphe connexe orienté.
– G contient un chemin Eulérien de a vers b si et seulement si d+ (a) = d− (a) + 1, d+ (b) =
d− (b) − 1,et ∀u 6= a, b, d− (u) = d+ (u).
– G contient un circuit Eulérien si et seulement si G est pseudosymétrique (i.e. ∀u ∈ V, d− (u) =
d+ (u)).
Chapitre 2. Cheminements dans les graphes 31
F IGURE 2.18 – Un graphe qui contient un chemin F IGURE 2.19 – Un graphe qui contient un circuit
Eulérien du sommet 5 au sommet 4. Eulérien.
5 Cheminements Hamiltoniens
Définition 5.1. Soit G = (V, E) un graphe connexe.
– Un cheminement (chaîne, chemin, cycle, circuit) est dit Hamiltonien s’il utilise tous les
sommets de V une et une seule fois.
– Le graphe G est dir Hamiltonien s’il admet un cycle Hamiltonien.
F IGURE 2.20 – Un graphe qui contient un circuit F IGURE 2.21 – Un graphe qui contient une chaîne
Hamiltonien Hamiltonienne.
Le théorème suivant donne une condition nécessaire que tout graphe Hamiltonien vérifie. Il est
utilisé pour montrer qu’un graphe n’est pas Hamiltonien :
Théorème 5.1 .
Si G = (V, E) est un graphe simple Hamiltonien, alors pour tout ensemble non vide de sommets
S ⊂ V , le nombre de composantes connexes du sous graphe induit par V \ S est inférieur au nombre
de sommets de S.
Autrement dit,
∀S ⊂ V, p(GV \S ) ≤ |S|.
Chapitre 2. Cheminements dans les graphes 32
Exemple 5.1 .
Le graphe de la Figure 2.22 n’est pas Hamiltonien car il existe un ensemble de sommets S = {1, 4},
pour lequel le sous graphe induit par V \S contient 3 composantes connexes, autrement dit p(GV \S ) =
3 > |S| = 2 comme le montre le graphe de la Figure 2.23.
1 Introduction
On rencontre souvent le problème de recherche des plus courts chemins, soit directement, soit
comme sous problème dans de nombreuses applications, on peut citer, entre autres :
– les problèmes d’optimisation dans les réseaux (réseaux routiers et réseaux de télécommuni-
cations, réseaux informatiques,etc.),
– les problèmes d’investissement et de gestion de stock,
– quelques problèmes d’intelligence artificielle et reconnaissance de formes,
– les problèmes d’ordonnancement.
2 Définitions
2.1 Réseau
Soit G = (X, A) un graphe orienté connexe. On associe à chaque arc a ∈ U , un nombre
l(a) ∈ R appelé longueur de l’arc a et on appelle ainsi R = (X, A, l), un réseau.
Remarque 2.1 .
En pratique, la longueur d’un arc peut désigner un temps, un coût, un poids, une distance, une proba-
bilité, etc. C’est pourquoi il peut être aussi bien négatif que positif.
2.1.1 Racine
33
Chapitre 3. Problème de recherche des plus courts chemins 34
Un circuit C de R tel que l(C) < 0 est dit circuit absorbant. Par exemple, dans la réseau
représenté par la Figure 3.2, le circuit C = 1431 est absorbant car l(C) = −1 < 0.
Étant donné un réseau R = (X, A, l) avec r racine de R, on définit π(x) le potentiel du sommet
x comme la longueur minimum des chemins de r à x.
En particulier on a π(r) = 0.
Exemple 2.1 .
Soit R le réseau représenté dans la Figure 3.3.
Chapitre 3. Problème de recherche des plus courts chemins 35
Si on s’intéresse à calculer les longueurs des plus courts chemins du sommet 3 vers les autres
sommets, on a alors :
– π(3) = 0,
– π(1) = 0, π(2) = −3,
– π(4) = 1, π(5) = 1,
– π(6) = −2
Comme le montre la Figure 3.4.
4 Position du problème
Étant donné un réseau R = (X, A, l), on distingue trois types de problèmes de recherche des
plus courts chemins :
Problème A : Étant donnés s et p deux sommets, on veut trouver un plus court chemin de s à p.
Théorème 4.1 .
Une condition nécessaire et suffisante pour que le problème A possède une solution est que :
(a) L’ensemble Y des sommets qui sont à la fois des descendants de s et ascendants de p soit
non vide, Y = D(s) ∩ A(p) 6= ∅,
(b) Le sous-réseau construit sur Y ne contient pas de circuit absorbant.
Problème B : Le sommet s étant donné, on veut trouver le plus court chemin de s à x, pour tout sommet x de
R
Théorème 4.2 .
Une condition nécessaire et suffisante pour que le problème B possède une solution est que :
(a) Le sommet s est une racine,
(b) R ne contient pas de circuit absorbant.
Problème C : Trouver un plus court chemin de x à y, pour toute paire de sommets x, y dans R
Théorème 4.3 .
Une condition nécessaire et suffisante pour que le problème C possède une solution est que :
(a) R soit fortement connexe,
(b) R ne contient pas de circuit absorbant.
Remarque 4.1 .
Contrairement à ce qui paraît évident, le problème B est plus facile à résoudre que le problème A,
donc pour résoudre le problème A, on passe par la résolution du problème B.
Aussi, le problème C peut être résolu en passant par la résolution de n problèmes B.
Nous allons donc nous intéresser uniquement aux algorithmes de résolution du problème B.
L’algorithme de Bellman consiste à calculer pour chaque sommet x ∈ X, son potentiel π(x)
qui représente la longueur d’un chemin optimal reliant s à x en se basant sur les prédécesseurs de
x, N − (x). Pour pouvoir calculer π(x), nous devons tout d’abord calculer au préalable π(y) avec y
prédécesseur de x. Ensuite parmi tous les chemins qui mènent à x, on choisit celui qui est de longueur
minimale.
Exemple 5.1 .
Trouver les plus courts chemins issus du sommet 1 dans le réseau R = (X, U, l) suivant :
Chapitre 3. Problème de recherche des plus courts chemins 38
F IGURE 3.6
Chapitre 3. Problème de recherche des plus courts chemins 39
L’algorithme de Dijkstra calcule les plus courts chemins issus du sommet s de proche en proche.
à partir d’un sommet t, il permet d’ajuster les valeurs de π(y) où y est successeur du sommet t s’il
trouve un chemin meilleur. La Figure 3.7 donne une illustration de l’algorithme de Dijkstra.
Exemple 5.2 .
On cherche les plus courts chemins issus du sommet 5 dans le réseau suivant :
Comme ce réseau contient des circuits et les longueurs des arcs sont positives on applique
l’algorithme de Dijkstra.
– Initialisation : S ← 5; Arc(x) ← ∅ ; π(x) ← +∞, ∀x 6= 5 ; π(5) ← 0; t ← 5 ;
– Itération 1 : t = 5
– y = 1 : π(5)+l(51) = 2 < π(1) = +∞ ⇒ π(1) ← π(5)+l(51) = 0+2; Arc(1) ← {51} ;
– y = 2 : π(5)+l(52) = 3 < π(2) = +∞ ⇒ π(2) ← π(5)+l(52) = 0+3; Arc(2) ← {52} ;
– y = 4 : π(5)+l(54) = 1 < π(4) = +∞ ⇒ π(4) ← π(5)+l(54) = 0+1; Arc(4) ← {54} ;
– y = 6 : π(5)+l(56) = 0 < π(2) = +∞ ⇒ π(2) ← π(5)+l(56) = 0+0; Arc(6) ← {56} ;
– y = 7 : π(5)+l(57) = 2 < π(7) = +∞ ⇒ π(7) ← π(5)+l(57) = 0+2; Arc(7) ← {57} ;
Choix de z : z ← 6 ; S ← S ∪ {6}; t ← 6
– Itération 2 : t = 6
– y = 2 : π(6) + l(62) = 2 < π(2) = 3 ⇒ π(2) ← π(6) + l(62) = 2; Arc(2) ← {62} ;
– y = 7 : π(6) + l(67) = 1 < π(7) = 2 ⇒ π(7) ← π(7) + l(67) = 1; Arc(7) ← {67} ;
Choix de z : z ← 4 ; S ← S ∪ {4}; t ← 4
– Itération 3 : t = 4
– y = 1 : π(4) + l(41) = 1 < π(1) = 2 ⇒ π(1) ← π(4) + l(41) = 1; Arc(1) ← {41} ;
– y = 7 : π(4) + l(47) = 2 ≮ π(7) = 1
Choix de z : z ← 7 ; S ← S ∪ {7}; t ← 7
– Itération 4 : t = 7
– Il n y a pas de successeurs du sommet 7
Choix de z : z ← 1 ; S ← S ∪ {1}; t ← 1
– Itération 5 : t = 1
– y = 2 : π(1) + l(12) = 2 ≮ π(2) = 2
Choix de z : z ← 2 ; S ← S ∪ {2}; t ← 2
– Itération 6 : t = 2
– y = 3 : π(2) + l(23) = 3 < π(3) = +∞ ⇒ π(3) ← π(2) + l(23) = 3; Arc(3) ← {23} ;
Choix de z : z ← 3 ; S ← S ∪ {3}; t ← 3 S = X ⇒ arret ← V RAI
Chapitre 3. Problème de recherche des plus courts chemins 41
Fin de l’algorithme.
Les plus courts chemins du sommet 5 aux autres sommets du réseau sont représentés dans la
figure suivante :
6.1 Introduction
On dit que l’on a affaire à un problème d’ordonnancement lorsqu’il faut planifier, en vue d’op-
timiser un certain critère, un projet P qui est constitué d’un ensemble de tâches ou opérations. Ces
tâches sont souvent liées par certaines contraintes de temps et de relations de précédence.
L’objectif est alors de proposer un calendrier pour l’exécution de ces tâches qui respecte les
contraintes imposées et optimise le critère donné.
Dans l’industrie, le bâtiment, sur les gros chantiers, les problèmes d’ordonnancement sont sou-
vent très présents, et de leur solution peut dépendre la réussite du projet.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
F IGURE 3.8
Algorithme de recherche du calendrier des tâches dans le réseau Potentiel-tâches. Cet algo-
rithme nous permet de calculer la durée minimale requise pour la réalisation d’un projet P ainsi que
les dates au plus tôt et au plus tard pour le commencement de chaque tâche de ce projet.
Algorithme Calcul du calendrier des dates au plus tôt et des dates au plus tard dans un réseau
potentiel-tâche
Entrée: le réseau potentiel-tâche associé à un projet P .
Sortie: Calendrier de réalisation des tâches et la durée optimale pour la réalisation de P
S ← {s} ; ts ← 0
Pour tout sommet x tel que N − (x) ⊂ S Faire
tx ← maxy∈N − (x) [ty + l(yx)]
S ← S ∪ {x}
Fin Pour
S ← {p} ; Tp ← tp
Pour tout sommet x tel que N + (x) ⊂ S Faire
Tx ← miny∈N + (x) [Ty − l(xy)]
S ← S ∪ {x}
Fin Pour
Le calendrier des dates au plus tôt et des dates au plus tard est donné par l’intervalle [tx , Tx ].
La durée optimale pour la réalisation du projet est égal à Tp = tp .
Exemple 6.3 .
En appliquant cet algorithme au réseau présenté par la Figure 3.8, on a :
– tA ← 0 ; tB ← 8 ; tC ← 8 + 4 = 12 ; tD ← 8 ; tE ← max[12 + 2; 8 + 9] = 17 ;tF ←
max[12 + 2; 8 + 9] = 17 ; tp ← max[17 + 3; 17 + 2] = 20 ;
– Tp ← 20 ; TE ← 20 − 3 = 17 ; TF ← 20 − 2 = 18 ; TC ← min[17 − 2; 18 − 2] = 15 ;
TD ← min[17 − 9; 18 − 9] = 8 ; TB ← 15 − 4 = 11 ;TA ← min[11 − 8; 8 − 8] = 0 ; Ts ← 0 ;
La durée optimale pour la construction de cette maison est de 20 semaines.
Le calendrier des dates au plus tôt et des dates au plus tard est alors donné par
Chapitre 3. Problème de recherche des plus courts chemins 45
Tâche ti Ti
A 0 0
B 8 11
C 12 15
D 8 8
E 17 17
F 17 18
– Dans ce réseau, les arcs représentent les tâches du projet et les sommets représentent des
étapes qu’on définit au fur et à mesure de la construction du réseau.
– On définit une étape début du projet xD et une étape fin du projet xF et un certain nombre
d’étapes intermédiaires.
– Si une tâche j doit succéder à une tâche i directement, alors l’extrémité initiale de l’arc aj est
l’extrémité terminale de l’arc ai .
Exemple 6.4 .
Le réseau PERT associé à l’exemple 6.2 est représenté comme suit :
F IGURE 3.9
Algorithme de recherche des dates au plus tôt et des dates au plus tard dans le réseau PERT
Le principe de cet algorithme est de calculer la date au plus tôt, notée π(x), et la date au plus tard,
notée θ(x) pour le commencement de chaque étape x du projet et en déduire par la suite le calendrier
des tâches.
Chapitre 3. Problème de recherche des plus courts chemins 46
Algorithme Calcul du calendrier des dates au plus tôt et des dates au plus tard dans un réseau PERT
Entrée: le réseau PERT associé à un projet P .
Sortie: Calendrier de réalisation des tâches et la durée optimale pour la réalisation de P
S ← {xD } ; π(xD ) ← 0
Pour sommet x ∈ / S tel que N − (x) ⊂ S Faire
π(x) ← maxa∈A|x=T (a) [π(I(a)) + l(a)]
S ← S ∪ {x}
Fin Pour
S ← {xF } ; θ(xF ) ← π(xF )
Pour sommet x ∈ / S tel que N + (x) ⊂ S Faire
θ(x) ← mina∈A|x=I(a) [θ(T (a)) − l(a)]
S ← S ∪ {x}
Fin Pour
Pour arc a ∈ A Faire
ta ← π(I(a))
Ta ← θ(T (a)) − l(a)
Fin Pour
Le calendrier des dates au plus tôt et des dates au plus tard est donné par l’intervalle [ta , Ta ].
La durée optimale pour la réalisation du projet est égale à π(xF ) = θ(xF ).
Exemple 6.5 .
Reprenons l’exemple 6.2 qui est représenté par le réseau PERT de la Figure 3.9. en appliquant l’algo-
rithme donné ci-dessus, on obtient :
– π(xD ) ← 0 ; π(x1 ) ← 8 ; π(x2 ) ← 12 ; π(x3 ) ← max[12 + 2; 8 + 9] = 17 ; π(xF ) ←
max[17 + 3; 17 + 2] = 20
– θ(XF ) = π(xF ) = 20 ; θ(x3 ) ← min[20 − 2; 20 − 3] = 17 ; θ(x2 ) ← 17 − 2 = 15 ;
θ(x1 ) ← min[15 − 2; 17 − 9] = 8 ; θ(xD ) ← 0 ;
Le calendrier des tâches se présente alors comme suit :
Tâche ti Ti
A 0 0
B 8 11
C 12 15
D 8 8
E 17 17
F 17 18
Chapitre 4
1 Introduction
Les flots permettent de modéliser une très large classe de problèmes. Leur interprétation cor-
respond à la circulation de flux physiques sur un réseau : distribution électrique, réseau d’adduction,
acheminement de paquets sur Internet, etc. En général, il s’agit d’acheminer une quantité de matière
dans le réseau et il n’y a ni perte ni création de matière lors de l’acheminement : pour chaque sommet,
le flux entrant doit être égal au flux sortant. Les liens qui permettent d’acheminer les flux ont une
capacité limitée.
2 Quelques définitions
∀x ∈ X, F + (x) = F − (x).
Autrement dit, la quantité de flux entrante à un sommet x est égale à celle sortante (principe de
conservation de la loi de Kirchhoff sur les nœuds).
47
Chapitre 4. Problèmes de flots dans les réseaux 48
Exemple 2.1 .
Dans le graphe suivant, le vecteur f = (1, 1, −2, 2, −3, −1, 2) est un flot, car pour tout sommet x, on
a la quantité de flux rentrante est égale à la quantité de flux sortante.
Si on ne peut pas trouver une telle chaîne, alors le flot f est maximum.
Chapitre 4. Problèmes de flots dans les réseaux 50
f (a) + ε si a ∈ C + ∪ {ar }
f (u) = f (a) − ε si a ∈ C −
f (a) sinon
Exemple 3.1 .
On veut trouver un flot maximum de 1 à 6 dans le réseau 4.1.
Comme nous n’avons aucun flot initial, nous posons f (a) = 0, ∀a ∈ A et on ajoute l’arc
ar = 61 avec c(61) = +∞ et f (ar ) = 0.
Itération 1 : Y ← {1} ; après procédure de marquage on a Y = {1, 2, 3, 4, 5, 6}
C = 1236,
Chapitre 4. Problèmes de flots dans les réseaux 51
F IGURE 4.1
Arbres et arborescences
1 Arbres
Définition 1.1. Soit G = (X, E) un graphe connexe tel que |V | = n et |E| = m.
Un arbre couvrant ou arbre de G est un graphe partiel T = (V, F ) connexe et sans cycles.
Une forêt est un graphe partiel sans cycles.
Exemple 1.1 .
54
Chapitre 5. Arbres et arborescences 55
On souhaite relier certaines villes qu’on dénote A, B, C, D , E et F par un nouveau type de fibre
optique. Les nouveaux câbles ne peuvent être enterrés que dans des tranchées déjà creusées entre les
différentes villes (voir Figure 5.4, où les nombres sur les arêtes représentent la longueur des tranchées
en kilomètres).
F IGURE 5.4 – Représentation des tranchées qui sont déjà creusées entre les six villes.
L’objectif est alors de déterminer dans quelles tranchées enterrer les câbles de manière à ce que
toutes les villes soient reliées, tout en minimisant le coût de l’installation qui dépend linéairement de
la longueur de câble utilisée.
Il est clair que si on veut minimiser le coût de l’installation, on éviterait de reconnecter une
ville où les câbles sont déjà installés. Par conséquent, le problème se ramène donc à la recherche un
graphe partiel connexe et sans cycles (arbre), dont le poids (égal la somme des poids des arêtes) est
minimum.
Définition 1.2. Étant donné un graphe connexe G = (V, E). Soit p une application définie par
p: E → R
e 7→ p(e)
Le problème de recherche d’un arbre de poids minimum dans G, revient à trouver un arbre T
pour lequel on a :
X
p(T ) = p(e) = min p(T́ ).
T́ , arbre de G
e∈T
Chapitre 5. Arbres et arborescences 56
Principe de l’algorithme. Soit G = (V, E) un graphe connexe où chaque arête ou arc est muni
d’un poids p(e). L’algorithme retrouve un arbre de poids minimum Tmin dans G, en sélectionnant des
arêtes dont le poids est petit, tout en évitant de créer un cycle.
L’algorithme de Kruskal.
Exemple 1.2 .
On reprend l’exemple d’introduction présenté dans 1.2.1 : L’application de l’algorithme de Kruskal à
cet exemple donne :
Tri des arêtes : e1 = EF, e2 = EC, e3 = AE, e4 = EB, e5 = BC, e6 = F D, e7 =
CD, e8 = CF, e9 = AB.
– Tmin ← ∅ ; p(Tmin ) ← 0 ; k ← 0 ; i ← 1 ; trouv ← F AU X
i = 1 : Tmin ∪ {e1 } ne contient pas de cycles alors Tmin ← Tmin ∪ {EF } ; p(Tmin ) ← 128 ;
k←1
i = 2 : Tmin ∪ {e2 } ne contient pas de cycles alors Tmin ← Tmin ∪ {EC} ; p(Tmin ) ← 128 +
140 = 268 ; k ← 2
Chapitre 5. Arbres et arborescences 57
i = 3 : Tmin ∪ {e3 } ne contient pas de cycles alors Tmin ← Tmin ∪ {EA} ; p(Tmin ) ← 268 +
210 = 478 ; k ← 3
i = 4 : Tmin ∪ {e4 } ne contient pas de cycles alors Tmin ← Tmin ∪ {EB} ; p(Tmin ) ← 478 +
245 = 723 ; k ← 4
i = 5 : Tmin ∪ {e5 } contient un cycle
i = 6 : Tmin ∪ {e6 } ne contient pas de cycles alors Tmin ← Tmin ∪ {DF } ; p(Tmin ) ← 723 +
273 = 996 ; k ← 5
i = 7 : k = 5 = 6 − 1 alors trouv ← V RAI.
Donc pour trouver l’installation la moins couteuse, il faut choisir les tranchées {EF, EC, EB, AE, F D}
avec une longueur total des câbles qui est égale à 996 Km.
L’algorithme de Prim.
Exemple 1.3 .
On applique l’algorithme de Prim sur l’exemple d’introduction 1.2.1 :
2 Arborescence
Définition 2.1. Une arborescence B du graphe G = (X, A) est un arbre de G muni d’une racine r.
Exemple 2.1 .
On veut trouver l’arborescence de racine 5 de poids minimum dans le graphe suivant : On a :
– p(Bmin ) ← 0 ; connexe = F AU X
– Bmin = {71, 62, 23, 36, 14, 47} ; p(Bmin ) = 3
Le graphe partiel F = (X, Bmin ) n’est pas connexe, donc il y a au moins un circuit dans F
(Figure 5.7).
– C = 236
Chapitre 5. Arbres et arborescences 61
F IGURE 5.7
– Choix de yx :
– 12 : p(12) − p(62) = 2
– 13 : p(13) − p(23) = 1
– 56 : p(56) − p(36) = 1
On choisit soit l’arc 13 ou l’arc 56. (on choisit 31)
– Bmin ← Bmin ∪ {13} \ {23} ; p(Bmin ) ← 3 − 1 + 2 = 4
F IGURE 5.8
Le graphe partiel F = (X, Bmin ) n’est pas connexe, donc il y a au moins un circuit dans F
(Figure 5.8).
– C = 147
– Choix de yx :
– 51 : p(51) − p(71) = 1
– 54 : p(54) − p(14) = 1
– 57 : p(57) − p(47) = 2
– 67 : p(67) − p(47) = 1
Chapitre 5. Arbres et arborescences 62
F IGURE 5.9
Le graphe partiel F = (X, Bmin ) est pas connexe, donc Bmin est une arborescence de poids
minimum (Figure 5.9).
Bibliographie
63