OR

Un peu d’Histoire…
La ville de Koeninsberg (aujourd’hui Kaliningrad) est traversée par la
Pregel, qui coule de part et d’autre de l’île de Kneiphof, et possède
sept ponts.
Question posée à Euler en 1736 : Peut-on visiter tous les quartiers de
la ville en ne traversant chaque pont qu’une seule fois ?

c
b

2
Applications
• Cartographie
Réseau routier, réseau internet, …
• Économie – Gestion
Planning de livraisons, gestion de flots, ordonnancement,
…
• Chimie – Biologie
Modélisation de molécules, ADN, …
• Sciences Sociales
Généalogie, phénomènes de masse, conflits, …
• Linguistique
Grammaire, Compilation, …
• Intelligence Artificielle
Comportement, …
3
Théorie des ensembles
[D1] Un ensemble est une collection d’objets. Un ensemble fini
se définit à partir de l’énumération de ses éléments.
X = {x1,x2 , … ,xn}
L’ensemble vide est noté .

[D2] La cardinalité d’un ensemble X, notée |X| ou Card X, est le

nombre des éléments de X.
Pour un ensemble infini X, |X| = ∞.

[D3] P(X) est l’ensemble des parties (sous-ensembles) de X.

[E1] X = {a,b,c}
P(X) = { ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c} }
[T1] Cardinalité de P(X) : |X| = n  |P(X)| = 2n.
4
Théorie des ensembles
[D4] La formule x  X signifie que x appartient à l’ensemble X.
La formule x  X signifie que x n’appartient pas à l’ensemble X.

[D5] Soient A,B  P(X).

A est inclus dans B, noté A  B, si tous les éléments de A sont des
éléments de B.
AB  xAxB

A est égal à B, noté A = B, si A est inclus dans B et B inclus dans A.

A = B  A  B et B  A

5
Opérations ensemblistes
[D6] Soient A,B  P(X). On peut construire de nouveaux
éléments de P(X) à l’aide des opérations suivantes :
• La réunion de A et B
A  B = { x  X : x  A ou x  B }

• L’intersection de A et B
A  B = { x  X : x  A et x  B }

• La différence de A et B
A - B = { x  X : x  A et x  B }

X – A est aussi appelé le complémentaire de A dans X.

6
Parties de X à k éléments
[D7] Pk(X) est l’ensemble des parties (sous-ensembles) de X à k
éléments.
[E2] X = {a,b,c}
P1(X) = { {a},{b},{c} }
P2(X) = { {a,b},{a,c},{b,c} }
P3(X) = { {a,b,c} }

[T2] Réunion des parties de X à k éléments :

|X| = n  P(X) =   P1(X)  P2(X)  …  Pn(X)

7
Produit cartésien d’ensembles
[D8] Soient A,B  P(X). On définit le produit cartésien de A et
B, noté A  B, de la façon suivante :
A  B = { (a,b) : a  A et b  B }
Un élément de l’ensemble A  B est appelé un couple.

Par abus de notation,

l’ensemble X n est le résultat
B AB de n produits cartésiens de
X.
b (a,b)
[E3] X2=XX
X3=XXX
A
a X4=XXXX
8
Application sur X
[D9] Une application univoque  sur X associe à tout élément x
de X un unique élément (x) de X. ( : X  X)

[E4] La fonction x  sin x est une application univoque sur .

[D10] Une application multivoque  sur X associe à tout élément

x de X un sous-ensemble (x) d’éléments de X. ( : X  P(X))

[E5] Si X est l’ensemble des personnes d’une même famille.

L’application qui à un individu x associe l’ensemble de ses enfants
est une application multivoque sur X.

9
Graphe
[D11] Un graphe G est défini par :
• Un ensemble de sommets X.
• Une application multivoque  sur X qui, à chaque sommet x,
associe le sous-ensemble (x) des sommets atteignables depuis x.
(x) est l’ensemble des successeurs de x.

On utilise alors la notation : G = (X, )

[D12] L’ordre du graphe G, noté |G|, est le nombre de sommets

du graphe. (|G| = |X| )

10
Lien entre successeurs et prédécesseurs
A partir de l’ensemble des successeurs de chaque sommet x de X, on
peut définir l’ensemble des prédécesseurs de x :
[D13] Un sommet y est un prédécesseur du sommet x si
x appartient à l’ensemble des successeurs de y. L’ensemble des
prédécesseurs de x est donné par la formule suivante :
-1(x) = { y  X : x  (y) }

[E6] X = {a,b,c,d,e}
(a) = {d} -1(a) = { x  X : a  (x) } = {b,e}
(b) = {a} -1(b) = { x  X : b  (x) } = {e}
(c) = {e} -1(c) = { x  X : c  (x) } = {d}
(d) = {c,e} -1(d) = { x  X : d  (x) } = {a}
(e) = {a,b} -1(e) = { x  X : e  (x) } = {c,d}
11
Graphe non orienté
[D14] Un graphe G = (X, ) est non orienté si :
Pour tout sommet x de X, chacun de ses successeurs y a x pour
successeur.
 x  X : y  (x)  x  (y)
[E7] Soit X l’ensemble des étudiants présents. (x) est
l’ensemble des voisins de l’étudiant x sur la même rangée.

(x) = {w,y}
w x y z
(y) = {x,z}
arête {x,y}

Dans un graphe non orienté, les relations bilatérales entre sommets

sont décrites par les arêtes de A  P2(X). On note alors G = (X,A).

12
Graphe orienté
[D15] Un graphe G = (X, ) est orienté si il n’est pas non orienté.

[E8] Soit X l’ensemble des étudiants présents. (x) est l’ensemble

des voisins de droite de l’étudiant x sur la même rangée.

(x) = {y}
w x y z
arc (x,y) (y) = {z}

Dans un graphe orienté, les relations unilatérales entre sommets

sont décrites par les arcs de U  X 2. On note alors G = (X,U).
[D16] Dans un arc (x,y) de U, x est l’extrémité initiale et y est
l’extrémité terminale.
13
Illustration
[E9] X = {a,b,c,d,e,f} a d
(a) = {d}
(b) = {a} e
(c) = {e}
(d) = {c,e} c
b
(e) = {a,b}
(f) = 
f

Graphe orienté ou non orienté ?

X = {a,b,c,d,e,f}
U = { (a,d) , (b,a) , (c,e) , (d,c) , (d,e) , (e,a) , (e,b) }
14
Adjacence de sommets
[D17] Deux sommets xi et xk de X sont adjacents si xi est un
successeur de xk ou xk est un successeur de xi.

xi adjacent à xk  xi  (xk) ou xk (xi)

Dans un graphe non orienté :  a  A : a = {xi , xk}

Dans un graphe orienté :  u  U : u = (xi , xk) ou u = (xk , xi)

15
Matrice d’adjacence dans un graphe orienté
x1 x2 … xn
Aij = 1 si (xi,xj)  U
0 0 x1
= 0 sinon
1 0 x2

A= …

0 xn

[T3] Deux sommets xi et xj sont adjacents sssi Aij = 1 ou Aji = 1.

[T4] La matrice d’adjacence d’un graphe non orienté G = (X,A) est
symétrique.
16
Degré d’un sommet dans un graphe orienté
[D18] Un arc u  U est un arc incident à x vers l’extérieur si
l’extrémité initiale de u coïncide avec le sommet x  X. On note
Ux+ l’ensemble des arcs incidents à x vers l’extérieur.

Un arc u  U est un arc incident à x vers l’intérieur si

l’extrémité terminale de u coïncide avec le sommet x  X. On note
Ux- l’ensemble des arcs incidents à x vers l’intérieur.

[D19] Le demi-degré extérieur de x, noté d + (x), est le nombre

d’arcs incidents à x vers l’extérieur. d + (x) = |Ux+|.

Le demi-degré intérieur de x, noté d-(x), est le nombre

d’arcs incidents à x vers l’intérieur. d - (x) = |Ux-|.

Le degré de x, noté d(x), est le nombre des arcs ayant une

extrémité coïncidant avec x. d(x) = d - (x) + d + (x).
17
Illustration graphique
Demi-degré extérieur de e : a d

d + (e) = 2
e
Demi-degré intérieur de e :
d - (e) = 3 b c

Degré de e :
d (e) = 2 + 3 f

18
Degré d’un sommet et matrice d’adjacence

x1 … xk … xn

0 0 x1

… …

A= 1 … 0 … 0 xk

d +(xk) … …

1 0 xn
d - (xk)

19
Adjacence d’arcs (Graphe orienté)
[D20] Deux arcs ui et uk de U sont semi-adjacents s’ils ont un
sommet en commun.
Deux arcs ui et uk de U sont adjacents si l’extrémité finale de
ui coïncide avec l’extrémité initiale de uk .

[E10] G = (X,U) un graphe orienté avec X = {x,y,z} et U = {u,v,w}

u v
x y z
w

Les arcs u et v sont adjacents.

Les arcs u et w sont semi-adjacents.
Les arcs v et w sont aussi adjacents.
20
Chaînes et Chemins (Graphe orienté)
[D21] Une chaîne c est une séquence (u1 , u2 , … , um) d’arcs telle
que : uk est semi-adjacente à uk+1 pour k, 0 < k < m.
Une chaîne simple est une chaîne dont les arêtes sont toutes
distinctes.
Un cycle est une chaîne simple dont l’extrémité initiale du
premier arc u1 coïncide avec l’extrémité finale du dernier arc um.

[D22] Un chemin c est une séquence (u1 , u2 , … , um) d’arcs telle

que : uk est adjacente à uk+1 pour k, 0 < k < m.
Un chemin simple est un chemin dont les arêtes sont toutes
distinctes.
Un circuit est un chemin simple dont l’extrémité initiale du
premier arc u1 coïncide avec l’extrémité finale du dernier arc um.
21
Retour à Koeninsberg
[D23] Une chaîne eulerienne est une chaîne simple contenant
toutes les arêtes d’un graphe non orienté G = (X,A).

c
b

[T5](Euler) Il n’existe pas de chaîne eulerienne dans le graphe de

Koeninsberg .

22
Lien entre chemins et matrice d’adjacence
Carré de la matrice d’adjacence A2 = A  A

A2ij = Ai1  A1j + … + Aik  Akj + … + Ain  Anj

 0 si Aik = 1 et Akj = 1
si xi a pour successeur xk
xk a pour successeur xj
A2ij = nombre de chemins de longueur 2 de xi vers xj

[T6] Si A est la matrice d’adjacence d’un graphe orienté G = (X,U).

Apij = nombre de chemins de longueur p de xi vers xj.
23
Fermeture transitive
[D24] Soit G = ( X , U ) un graphe orienté d’ordre n. La fermeture
transitive T du graphe est une matrice définie comme suit :

T = A + A2 + A3 + … + An-1

[T7] Tij correspond au nombre de chemins (de longueur

inférieure ou égal à n-1) depuis xi vers xj dans le graphe G.

[T8] Si Tij = 0 alors il n’existe aucun chemin de xi vers xj dans le

graphe G.

24
Complexité du calcul de la fermeture transitive
[T9] La complexité du calcul de la fermeture transitive est
d’ordre 4 : le temps de calcul est proportionnel à n4 où n est l’ordre
du graphe (nombre de sommets du graphe).
T = A + A2 + A3 + … + An-1
[Preuve de T9] Le calcul de la fermeture transitive T nécessite :
• (n-2) multiplications de matrices
– (n-2)n3 additions et (n-2)n3 multiplications n n2 n3 n4
• (n-2) additions de matrices 10 100 1000 10 000
– (n-2)n2 additions 100 10 000 106 108
1000 106 109 1012

Finalement, 2 (n-2)n3 + (n-2)n2 ≈ kn4 opérations.

25
Optimisation du calcul de la fermeture transitive
[D25] Une matrice booléenne est une matrice dont les coefficients
sont des variables booléennes (V pour Vrai, F pour Faux).

[D25b] Une matrice de fermeture transitive représentée par une

matrice booléenne permet uniquement de savoir s’il existe un
chemin entre deux sommets du graphe. Mais on ignore combien?

A B A▼B A▲B
V V V V
V F V F
F V V F
F F F F

26
Optimisation du calcul de la fermeture transitive
[A1] Algorithme de Warshall
Pour i de 1 à n
Pour j de 1 à n
Pour k de 1 à n
Tij = Tij ▼ (Tik ▲ Tkj)

[T10] La complexité de l’algorithme de Warshall est d’ordre 3.

[Preuve de T10] Le calcul de la fermeture transitive T nécessite :

n3 ‘OU logique’, n3 ‘ET logique’
Finalement, 2n3 opérations.

27
Parcours (en profondeur) d’un graphe
Objectif : déterminer l’ensemble des sommets atteignables depuis un
sommet source s.
[A2] Algorithme (récursif) de parcours d’un graphe
Visiter les successeurs du sommet s

Visiter un sommet t
Début
Si t n’a pas encore été visité Alors
Marquer t
Visiter les successeurs de t
FinSi
Fin
28
Exemple de parcours en profondeur
Déterminer l’ensemble Xa des sommets du graphe atteignables depuis
le sommet a.

a d Visiter d

Visiter c
c
Visiter b

b e Visiter a

Visiter e
f
Xa = { d , c, b, a, e }
29
Connexité (Graphe orienté)
[D26] La longueur d’une chaîne (ou d’un chemin) c, notée l(c),
correspond aux nombres d’arcs de la chaîne (ou du chemin).

[D27] Un graphe est faiblement connexe si, entre deux sommets

xi et xj quelconques, il existe une chaîne c = {u1 , … , um} de sorte
que xi est une des extrémités de u1 et xj une des extrémités de um.

[D28] Un graphe est fortement connexe si, entre deux sommets xi

et xj quelconques, il existe un chemin c = {u1 , … , um} qui
commence en xi et se termine en xj.

30
Composantes connexes d’un graphe
[D29] Une composante faiblement connexe d’un graphe est un
sous-ensemble Y de X tel que : entre deux sommets xi et xj
quelconques de Y, il existe une chaîne c = {u1 , … , um} de sorte
que xi est une des extrémités de u1 et xj une des extrémités de um.

[D30] Une composante fortement connexe d’un graphe est un

sous-ensemble Y de X tel que : entre deux sommets xi et xj
quelconques de Y, il existe un chemin c = {u1 , … , um} qui
commence en xi et se termine en xj.

[D31] Une composante fortement connexe maximale (cfcm) d’un

graphe est le plus grand sous-ensemble Y de X qui soit fortement
connexe.
31
Recherche de cfcm dans un graphe orienté
[A3] Algorithme de recherche d’une cfcm depuis un sommet
s

Marquer le sommet s du signe + -

Tant que l’on peut modifier les signes des sommets Faire
Marquer du signe + tout successeur d’un sommet marqué d’un +
Marquer du signe - tout prédécesseur d’un sommet marqué d’un -
FinFaire

L’ensemble des sommets marqués du signe + - constituent la

composante fortement connexe maximale issue du sommet s.

32
Exemple de recherche de cfcm
cfcm depuis le sommet a : { a , b , c }
cfcm depuis le sommet d : { d , e , f }
-
+-
b

+- +-
+ +
a c d e
+- +-
- -

f
+
+-
33
Graphe orienté valué
[D32] Un graphe orienté valué G est défini par :
• Un ensemble de sommets X.
• Un ensemble d’arcs U  X2.
• Une valuation V : U  R qui à chaque arc du graphe associe une
valeur réelle (poids).

On utilise alors la notation : G = ( X , U , V )

34
Exemple de graphe orienté valué

7
a d
4
2
3
1 4 e 3 f

5 1
b c

35
Recherche de chemins de poids minimal (resp.
maximal)

Méthodes en deux étapes :

• Détermination des poids minimaux (resp. maximaux) de chaque
sommet.
• Obtention du chemin minimal (resp. maximal) à l’aide des poids
des sommets.

36
Chemin de poids minimal
[A4] Algorithme de Ford

Initialisation
λ1 = 0 ;  j ≠1 λj = +∞

λj = λi + wij

OUI  (xi , xj)  U : NON

λj > λi + wij FIN

37
Chemin de poids maximal
[A5] Algorithme de Ford

Initialisation
λ1 = 0 ;  j ≠1 λj = - ∞

λj = λi + wij

OUI  (xi , xj)  U : NON

λj < λi + wij FIN

38
Chemin de poids minimal
[A6] Algorithme de Bellman-Kalaba
Initialisation
k=0
λ1(k) = 0 ;  j ≠ 1 λj(k) = +∞

k=k+1
λ1(k) = 0 ;  j ≠ 1 λj(k) = min {λi(k-1) + wij }

OUI  xj  X : NON
FIN
λj (k) ≠ λj (k-1)

39
Chemin de poids maximal
[A7] Algorithme de Bellman-Kalaba
Initialisation
k=0
λ1(k) = 0 ;  j ≠ 1 λj(k) = - ∞

k=k+1
λ1(k) = 0 ;  j ≠ 1 λj(k) = max {λi(k-1) + wij }

OUI  xj  X : NON
FIN
λj (k) ≠ λj (k-1)

40
Chemin de poids minimal
[A8] Algorithme de Dijkstra

Initialisation
D = { x1 } ; λ1 = 0 ;  j ≠ 1 λj = +∞

λk = min λj  xj  D
D = D  { xk } ; λj = min {λj , λk + wkj }  xj  D

NON
xn  D OUI
FIN
41
Chemin de poids minimal
[A9] Obtention du chemin à partir des poids minimaux

Initialisation
xk = xn ; C = ( xn )

Chercher xj  X : λk = λj + wjk
xk = xj
C = ( xk , C )

NON
xk = x1
OUI
FIN
42
Recherche de flots maximaux
Objectif : Faire transiter la plus grande quantité (information,
marchandise, personnes) d’une source vers une destination au sein
d’un réseau.

[D33] Un réseau avec capacités R = (X,U,C) d’ordre n est un

graphe orienté antisymétrique* valué dans lequel :
 -1(x1) = Ø x1 est le sommet entrée (source)
 (xn) = Ø xn est le sommet sortie (destination)

*  (xi,xj)  U  (xj,xi)  U (arc à sens unique)

Notation :  (xi,xj)  U : C(xi,xj) = Cij capacité de l’arc (xi,xj)

43
Exemple de réseau avec capacités

b
[3]
[7]

[5]
Entrée a [4] d e Sortie
[2]
[5]
[2]

44
Définition du flot réalisable
[D34] Un flot F sur un réseau avec capacités R = (X,U,C) est une
valuation de l’ensemble des arcs U. Le flot correspond à la
quantité qui transite sur le réseau.
Notation :  (xi,xj)  U : F(xi,xj) = Fij flot sur l’arc (xi,xj)

[D35] Un flot F sur R = (X,U,C) est réalisable s’il satisfait les

contraintes de :
1. Capacité des arcs
Le flot sur un arc ne dépasse pas la capacité de cet arc.
2. Conservation du flux (loi de Kirchoff)
La somme des flots entrant dans un sommet est égale à la
somme des flots sortant de ce sommet.

45
Définition du flot maximal
[D36] La valeur d’un flot F sur R = (X,U,C) correspond à la
quantité totale qui transite sur le réseau. La valeur du flot
correspond à la somme des flots sortant de l’entrée qui est égale à
la somme des flots convergeant vers la sortie (conservation du
flux).

[D37] Un flot F sur R = (X,U,C) est maximal si F est un flot

réalisable qui maximise la valeur du flot.

46
Construction du graphe d’écart
[D38] Un arc (xi,xj) du réseau R = (X,U,C) est saturé par le flot F
si :
Fij = Cij (capacité maximale atteinte)
[D39] Un arc (xi,xj) du réseau R = (X,U,C) est antisaturé par F si :
Fij = 0 (flot inexistant)

[D40] A partir du réseau R = (X,U,C) et d’un flot F, on peut

construire le graphe d’écart G = (X,F(U),E) qui traduit les
augmentations ou diminutions possibles du flot F dans le réseau.
 (xi,xj)  U :
Si Fij < Cij (non saturé) alors (xi,xj)  F(U) , Eij = Fij- Cij (augmentation)
Si Fij > 0 (non antisaturé) alors (xj,xi)  F(U) , Eji = Fij (diminution)
47
Exemple de graphe d’écart

b b
3 [3] 2
5 [7] 3
5
a 2 [4] d a 2 2 d
1
4 [5] 2 [2] 4 2

c c

Réseau R = (X,U,C) Graphe d’écart G =

(X,F(U),E)
48
Construction d’un flot maximal
[A10] Algorithme de Ford-Fulkerson
Initialisation du flot F : Fij = 0 (arcs antisaturés)
Fin = FAUX
Tant que NON Fin
Construction du graphe d’écart G = (X,F(U),E)
Recherche d’un chemin C dans G depuis l’entrée vers la sortie
Si C existe Alors
Calcul de l’augmentation
Affectation de l’augmentation
Sinon
Fin = VRAI

49