UNIVERSITE CHEIKH ANTA DIOP (UCAD)

ÉCOLE SUPÉRIEURE POLYTECHNIQUE (E.S.P)

DÉPARTEMENT DE GESTION

Recherche Opérationnelle

Chapitre: Théorie des Graphes

Arbre, graphe valué et niveau a

[Link]

2 juillet 2020
(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 1 / 16
Sommaire

1 Arbre et arborescence

2 Graphe valué
Algorithme de Kruskal

3 Niveaux dans un graphe

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 2 / 16

Arbre et arborescence

Definition
Un arbre T est un graphe connexe sans cycle. Il a une arête de moins que
de sommets.
Arborescence Une arborescence est un graphe orienté G=(S,A) tel que :
sans l’orientation G est un arbre
tous les sommets de G sont descendants d’un sommet unique r appelé
racine.
Anti-arborescence
Une anti-arborescence est le graphe ”inverse ” d’une arborescence : tous
les sommets sont ascendants d’un sommet a unique appelé anti-racine.
a

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 3 / 16

Arbre et arborescence

a
r

(b) Arborescence (c) Anti−arborescence

(a) Arbre

l’arborescence peut permettre de hiérarchiser les différents postes de

l’entreprise d’un PDG au gardien. a

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 4 / 16

Graphe valué
Exemple
La carte des différentes villes d’un pays peut être représentée sous forme
d’un graphe valué :
les sommets représentent les différentes villes du pays ;
les arêtes reliant deux villes peuvent représenter les distances entre
elles.

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 5 / 16

Graphe valué
Exemple
La carte des différentes villes d’un pays peut être représentée sous forme
d’un graphe valué :
les sommets représentent les différentes villes du pays ;
les arêtes reliant deux villes peuvent représenter les distances entre
elles.
ville 1 10
21
ville 2 4 ville 7
8 9
20 15
ville 5
11 ville 8
ville 3 14
18 15 11
25 ville 6 26
ville 4 8 ville 11
30
16 ville 9 23 a
11 [Link]
ville 10
(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 5 / 16
Arbre de recouvrement

Soit G = (S, A) un graphe connexe valué. Un graphe partiel T de G est un

arbre de recouvrement si T est un arbre contenant tous les sommets de G.
Arbre de recouvrement à coût minimal
Parmi tous les arbres de recouvrement d’un graphe G, celui dont la somme
total des coûts de ses arcs est la plus petite est appelé arbre de
recouvrement à coût minimal.

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 6 / 16

Arbre de recouvrement

Algorithme de Kruskal
1 Étape 1. Initialisation
Choisir un arc u1 ∈ A de coût minimal.
Poser i = 1 et P = {∅}
2 Étape 2. Addition d’arc
Poser P = P ∪ {ui } ;
Poser 1 ≤ i ≤ n − 1, déterminer ui+1 ∈ A privé de P tel que
(a) le coût de ui+1 soit minimal.
(b) le sous graphe Gi engendré par les arcs {u1 , u2 , ..., ui+1 } soit sans cycle
3 Étape 3. Mise à jour
poser i = i+1
Si i = n ou Gi = T , alors fin sinon retourner à l’étape 2.
a

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 7 / 16

Exemple
Appliquer l’algorithme de Kruskal au graphe suivant :
a b c
2 9

1 3 9

7 2 d
f e

Solution Première méthode

1 : Classer les arêtes dans 2 Initialisation : u1 = [a, f ],
l’ordre croissant de leur i = 1 et P = {∅}
valeurs. 3 addition d’arêtes Choisir
Arêtes Valeur choix d’autres arêtes en suivant
[a,f] 1 × l’ordre du tableau et sans
[a,b] 2 × créer de cycle.
[e,d] 2 × P=
[e,b] 3 × {[a, f ], [a, b], [e, d], [e, b], [b, c]}
[f,e] 7 Tous les sommets du
[b,c] 9 × graphe figurent dans P.
a

[c,d] 9 L’algorithme s’arrête.

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 8 / 16

L’arbre de recouvrement à coût minimal de l’exercice devient :

a b c
2 9

1 3

2 d
f e

Son coût :
C = 1+2+3+9+2 = 17

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 9 / 16

Arbre de recouvrement
Appliquons l’algorithme à la carte de la région suivante
ville 1 10
21
ville 2 4 ville 7
8 9
20 15
ville 5
11 ville 8
ville 3 14
18 15 11
25 ville 6 26
ville 4 8 ville 11
30
16 ville 9 23
11
ville 10

Solution
ville 1 10
21
ville 2 4 ville 7
8 9
20 15
ville 5
11 ville 8
ville 3 14
18 15 11
25 ville 6 26
ville 4 8 ville 11
30
16 ville 9 23
11
ville 10

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 10 / 16

Arbre de recouvrement
Appliquons l’algorithme à la carte de la région suivante
ville 1 10
21
ville 2 4 ville 7
8 9
20 15
ville 5
11 ville 8
ville 3 14
18 15 11
25 ville 6 26
ville 4 8 ville 11
30
16 ville 9 23
11
ville 10

Solution
ville 1 10 ville 1 10
21 21
ville 2 4 ville 7 ville 2 4 ville 7
8 9 8 9
20 15 20 15
ville 5 ville 5
11 ville 8 11 ville 8
ville 3 14 ville 3 14
18 15 11 18 15 11
25 ville 6 26 25 ville 6 26
ville 4 8 ville 11 ville 4 8 ville 11
30 30
16 ville 9 23 16 ville 9 23

ville 10
11
⇒ ville 10
11

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 10 / 16

Arbre de recouvrement
Appliquons l’algorithme à la carte de la région suivante
ville 1 10
21
ville 2 4 ville 7
8 9
20 15
ville 5
11 ville 8
ville 3 14
18 15 11
25 ville 6 26
ville 4 8 ville 11
30
16 ville 9 23
11
ville 10

Solution
ville 1 10 ville 1 10 ville 1 10
21 21 21
ville 2 4 ville 7 ville 2 4 ville 7 ville 2 4 ville 7
8 9 8 9 8 9
20 15 20 15 20 15
ville 5 ville 5 ville 5
11 ville 8 11 ville 8 11 ville 8
ville 3 14 ville 3 14 ville 3 14
18 15 11 18 15 11 18 15 11
25 ville 6 26 25 ville 6 26 25 ville 6 26
ville 4 8 ville 11 ville 4 8 ville 11 ville 4 8 ville 11
30 30 30
16 ville 9 23 16 ville 9 23 16 ville 9 23

ville 10
11
⇒ ville 10
11
⇒ ville 10
11

Le coût de cet arbre est de :4 +8+10+9+11+11+8+11+15+18= 103

Remarque : Une centrale d’eau peut procéder de la sorte pour distribuer
a
de façon optimale de l’eau à travers ses conduites. Dans ce cas la centrale
[Link]
se positionnerait dans la ville 5.
(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 10 / 16
Niveaux dans un graphe

Considérons un graphe orienté G = (S, A) connexe sans circuit.

Niveau d’un sommet
Le niveau d’un sommet x de G est la longueur (nombre d’arcs) du plus
long chemin d’extrémité finale x.

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 11 / 16

Niveaux dans un graphe

Considérons un graphe orienté G = (S, A) connexe sans circuit.

Niveau d’un sommet
Le niveau d’un sommet x de G est la longueur (nombre d’arcs) du plus
long chemin d’extrémité finale x.
Algorithmes de recherche de niveaux :
1 lister dans un tableau l’ensemble des sommets et leurs précédents (s’il
y en a) ;
2 déterminer l’ensemble Ni contenant les sommets n’ayant pas de
précédents. Poser i = 0 ;
3 rayer du tableau tous les sommets n’ayant pas de précédents.
S’il se trouve que tous les sommets du graphe sont barrés, alors c’est
la FIN de l’algorithme.
Sinon retourner à l’étape (2) a

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 11 / 16

Niveaux dans un graphe
Exemple : Ordonnancer par niveau le graphe suivant :
c

b e

g
a

d f

Etape 1
Sommets Précédent(s)
a b,d
b c,d,e
c e
d e, f
e f,g
f g
a
g -
N0 = {g } [Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 12 / 16

Niveaux dans un graphe
Exemple : Ordonnancer par niveau le graphe suivant :
c

b e

g
a

d f

Etape 1 Étape 2
Sommets Précédent(s) Sommets Précédent(s)
a b,d a b,d
b c,d,e b c,d,e
c e c e
⇒
d e, f d e, f
e f,g e f,S
g
f g f g
S
a
g - g
S -
N0 = {g } N1 = {f }
[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 12 / 16

Niveaux dans un graphe
Sommets Précédent(s)
a b,d
b c,d,e
c e
N2 = {e}
d e, fA
e fA ,S
g
fA g
S
g
S -

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 13 / 16

Niveaux dans un graphe
Sommets Précédent(s) Sommets Précédent(s)
a b,d a b,d
b c,d,e b c,d,eA
c e c eA N3 =
N2 = {e}
d e, fA d e,
A f
A {d, c}
e fA ,S
g eA fA ,S
g
fA g
S fA g
S
g
S - g
S -
Sommets Précédent(s)
a b,S d
b c,
A S,eA
d
cA eA N4 =
d
S e,
A A f {b}
eA fA ,Sg
fA g
S a

g
S - [Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 13 / 16

Niveaux dans un graphe
Sommets Précédent(s) Sommets Précédent(s)
a b,d a b,d
b c,d,e b c,d,eA
c e c eA N3 =
N2 = {e}
d e, fA d e,
A f
A {d, c}
e fA ,S
g eA fA ,S g
fA g
S fA g
S
g
S - g
S -
Sommets Précédent(s) Sommets Précédent(s)
a b,S d a bA ,Sd
b c,
ASA d , e b A c,
A S,eA
d
cA eA N4 = cA eA N5 =
⇒
d
S e,
A A f {b} d
S e,
A A f {a}
eA fA ,Sg eA fA ,Sg
fA g
S fA g
S a

g
S - g
S - [Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 13 / 16

Niveaux dans un graphe

Représentation du graphe en respectant les niveaux

g f d a

N N1 N2 N3 N4 N5
0

[Link]

(ESP/UCAD Mail : esp@[Link]) 2 juillet 2020 14 / 16