IUT de Reims-Châlons-Charleville rue des crayères, BP 1035 51687 Reims Cedex 2 Introduction à la Théorie des Graphes Olivier Nocent [email protected]

IUT de Reims-Châlons-Charlevillerue des crayères, BP 103551687 Reims Cedex 2

Introduction à laThéorie des Graphes

Olivier [email protected]

IUT de Reims-Châlons-Charleville [[email protected]] 2

C’est déjà Noël

Le cours « Introduction à la Théorie des Graphes » (au format PowerPoint et Acrobat Reader) est

disponible sur l’intranet du Département Informatique

http://nocent

http://leri.univ-reims.fr/~nocent

GRATUIT


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 traversant chaque pont qu’une seule fois ?

a

b

d

c


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, …


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.


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


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 BA B = { x X : x A ou x B }

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

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

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


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)


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.

A

B A B

a

b (a,b)

Par abus de notation, l’ensemble X n est le résultat de n produits cartésiens de X.

[E3] X 2 = X X

X 3 = X X X

X 4 = X X X X


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.


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| )


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}


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.

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).

w yx z(x) = {w,y}

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


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.

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.

w yx z(x) = {y}

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


Illustration[E9] X = {a,b,c,d,e,f}

(a) = {d}

(b) = {a}

(c) = {e}

(d) = {c,e}

(e) = {a,b}

(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) }

a d

b

f

e

c


Adjacence de sommets[D17] Deux sommets xi et xk de X sont adjacents si xi est un

successeur de xk ou si 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 = (xi , xk)


Matrice d’adjacence dans un graphe orienté

[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.

x1 x2 … xn

0 0 x1

1 0 x2

…

A = …

…

0 xn

Aij = 1 si (xi,xj) U

= 0 sinon


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).


Illustration graphique

a d

b

f

e

c

Demi-degré extérieur de e :

d + (e) = 2

Demi-degré intérieur de e :d - (e) = 3

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


Degré d’un sommet et matrice d’adjacence

x1 … xk … xn

0 0 x1

… …

A = 1 … 0 … 0 xk

… …

1 0 xn

d - (xk)

d +(xk)


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}

Les arcs u et v sont adjacents.

Les arcs u et w sont semi-adjacents.

Les arcs v et w sont aussi adjacents.

x y zu v

w


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.


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).

a

b

d

c

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


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.


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.


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-2) additions de matrices

– (n-2)n2 additions

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

n n2 n3 n4

10 100 1000 10 000

100 10 000 106 108

1000 106 109 1012


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


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.


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


Exemple de parcours en profondeur

a d

b

f

c

e

Déterminer l’ensemble Xa des sommets du graphe atteignables depuis le sommet a.

Xa = { d , c, b, a, e }

Visiter a

Visiter d

Visiter c

Visiter b

Visiter e


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.


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.


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.


Exemple de recherche de cfcm

a d

b

f

c e+ - -

+ -

+

+

+

++

-

+ -

+

-

-

-

-

cfcm depuis le sommet a :

cfcm depuis le sommet d :

{ a , b , c }

{ d , e , f }


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 )


Exemple de graphe orienté valué

a d

b

fe

c

1 43

2

5

7

3

1

4


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.


Chemin de poids minimal

[A4] Algorithme de Ford

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

(xi , xj) U :λj > λi + wij

λj = λi + wij

FINOUI NON


Chemin de poids maximal

[A5] Algorithme de Ford

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

(xi , xj) U :λj < λi + wij

λj = λi + wij

FINOUI NON



[A6] Algorithme de Bellman-Kalaba

Initialisationk = 0

λ1(k) = 0 ; j ≠ 1 λj(k) = +∞

xj X :λj (k) ≠ λj (k-1)

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

FINOUI NON


Chemin de poids maximal

[A7] Algorithme de Bellman-Kalaba

Initialisationk = 0

λ1(k) = 0 ; j ≠ 1 λj(k) = - ∞

xj X :λj (k) ≠ λj (k-1)

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

FINOUI NON



[A8] Algorithme de Dijkstra

InitialisationD = { x1 } ; λ1 = 0 ; j ≠ 1 λj = +∞

xn D

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

FINOUINON



[A9] Obtention du chemin à partir des poids minimaux

Initialisationxk = xn ; C = ( xn )

xk = x1

Chercher xj X : λk = λj + wjk

xk = xj C = ( xk , C )

FINOUINON


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)


Exemple de réseau avec capacités

a d

b

e

c

[5]

[4]

[7]

[2]

[5]

[2]

[3]

SortieEntrée


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 arcsLe 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.


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.


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)


Exemple de graphe d’écart

a d

b

c

4 [5]

2 [4]

5 [7]

2 [2]

3 [3]

a d

b

c

1

2

2

2

3

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

4

5

2


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

Documents

IUT de Reims-Châlons-Charleville rue des crayères, BP 1035 51687 Reims Cedex 2 Introduction à la Théorie des Graphes Olivier Nocent [email protected]