Table des matières - perso.usthb.dzperso.usthb.dz/~mboukala/CoursTG.pdf · Introduction générale La théorie des graphes est un très vaste domaine, en évolution constante tant

Table des matières

Introduction générale 4

1 Concepts fondamentaux des graphes 6

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.1 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.2 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.3 Représentation graphique . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Notion de degré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.1 Formule des degrés . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4 Représentation machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4.1 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4.2 Matrice d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.3 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.5 Graphes particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.5.1 Sous graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.5.2 Graphe partiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.5.3 Sous graphe partiel . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.5.4 Complément d’un graphe . . . . . . . . . . . . . . . . . . . . . . . 13

1.6 Propriétés des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.6.1 Graphe Simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.6.2 Graphe Complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.6.3 Graphe Régulier . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6.4 Graphe Symétrique . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6.5 Graphe Antisymétrique . . . . . . . . . . . . . . . . . . . . . . . . 14

1

1.6.6 Graphe Transitif . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6.7 Graphe Biparti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6.8 Graphe Multiparti . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.7 Stable / Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.8 Exploration d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.9 Isomorphisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Cheminement dans les Graphes 18

2.1 Chaînes / Chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.1 Chaîne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.2 Chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.3 Chaîne / Chemin simple . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1.4 Chaîne / Chemin élémentaire . . . . . . . . . . . . . . . . . . . . . 19

2.2 Cycles / Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.1 Chaîne fermée / Chemin fermé . . . . . . . . . . . . . . . . . . . . 20

2.2.2 Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.3 Représentation vectorielle d’un cycle . . . . . . . . . . . . . . . . . 20

2.2.4 Circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4 Composante connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.1 Graphe k-connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.5 Forte Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.5.1 Composantes fortement connexes (C.F.C.) . . . . . . . . . . . . . . 22

2.6 Algorithmes de calcul des composantes fortement connexes . . . . . . . . 22

2.6.1 Graphe réduit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.7 Cocycles et Cocircuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.7.1 Représentation vectorielle d’un cocycle . . . . . . . . . . . . . . . . 24

2.8 Parcours Eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.9 Parcours Hamiltoniens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3 Problèmes de cheminement dans les Graphes 27

3.1 Graphes sans circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.1 Source et Puits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.2 Partition en niveaux d’un graphe sans circuits . . . . . . . . . . . . . . . . 28

3

3.2.1 Niveau d’un sommet . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2.2 Partition en niveaux . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3 Graphe pondéré (Réseau) . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3.1 Poids d’un chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3.2 Circuit absorbant . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.4 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.4.2 Les données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.4.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.5 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.5.1 L’Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 Problèmes d’ordonnancement 32

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.2 contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.3 Les tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.4 Diagramme de Gantt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.5 Représentation par un graphe potentiels-tâches . . . . . . . . . . . . . . . 34

4.6 Recherche d’un ordonnancement optimale . . . . . . . . . . . . . . . . . . 35

4.7 Marges totales et chemin critique . . . . . . . . . . . . . . . . . . . . . . . 36

5 Arbres et Arborescences 37

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.2 L’arborescence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.3 Arbre couvrant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.4 Arbre couvrant de poids minimun . . . . . . . . . . . . . . . . . . . . . . 39

6 Les flots 41

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.2 Flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.3 Propriétés fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.3.1 Flot maximal et coupe minimale . . . . . . . . . . . . . . . . . . . 43

6.3.2 Graphe d’écart et chemin augmentant . . . . . . . . . . . . . . . . 43

Introduction générale

La théorie des graphes est un très vaste domaine, en évolution constante tant du

point de vue des applications que de celui des recherches fondamentales et constitue

aujourd’hui un corpus de connaissances très important. Ce cours ne constituera donc

qu’une introduction à cette théorie.

La théorie des graphes est née au dix-huitième siècle en essayant de trouver des

solutions à des exercies considŕés comme étant des curiosités mathématiques.

En 1736 Euler présenta une communication dans laquelle il proposait une solution

au célèbre problème des ponts de Kônigsberg. Le problème posé était le suivant. Deux

deltas C et D sur la rivière Pregel à Kônigsberg (Actuellement Kaliningrad) étaient

reliées entre elles ainsi qu’aux rivages A et B à l’aide de sept ponts comme le montre la

figure 1.

A

B

C D

Figure 1 – Problème des ponts de Kônigsberg

Le problème consistait, à partir d’un point quelconque A, B, C, ou D, à traverser

chacun des ponts une fois et une seule et à revenir au point de départ. Euler représenta

cette situation à l’aide d’un graphe et démontra que ce problème n’admet pas de solution.

Deux autres problèmes d’importance pour la théorie des graphes furent également

proposés.

Le premier est la conjecture des quatre couleurs qui affirme que quatre couleurs suff-

4

Introduction générale

isent pour colorier n’importe quelle carte plane telle que les pays ayant une frontière

commune soient de couleurs différentes. Ce problème est resté très longtemps sans solu-

tion. Il a fallu attendre jusqu’en 1976 pour que Appel et Haken prouvent ce théorème

en réduisant le problème à un nombre fini de situations particulières et en trouvant une

solution pour chacune d’entre elles à l’aide d’un ordinateur.

Le second problème est dû à Sir Hamilton. En 1859, il inventa un casse-tête qui

consiste en un dodécaèdre régulier en bois (un polyèdre à 12 faces et 20 sommets), chaque

face étant un pentagone régulier. Trois arêtes sont donc issues de chaque sommet. Un

clou est fiché sur chaque sommet marqué du nom de vingt grandes villes mondiales. Le

casse-tête consiste à enrouler une ficelle passant une fois et une seule fois par chacune des

villes (sommets). Bien que la solution de ce problème soit aisée à obtenir, personne n’a

encore trouvé de condition nécessaire et suffisante de l’existence d’un tel chemin (appelé

chemin Hamiltonien) dans un graphe quelconque.

Les graphes constituent donc à la fois une théorie et un outils qui permettent de

modéliser une grande variété de problèmes en se ramenant à l’étude de graphes. Les

derniers travaux en théorie des graphes sont aussi effectués par des informaticiens, du

fait de l’importance que revêt l’aspect algorithmique.

Les domaines d’applications des graphes sont diverses, justifiant une recherche im-

portante en algorithmique. On peut citer :

– Les réseaux de communication : réseaux routiers, de chemin de fer, de téléphone,

de relais de télévision, réseaux électriques, réseaux des informations dans une or-

ganisation, etc... ;

– La gestion de la production et les problèmes d’ordonnancement des tâches : Le

graphes potentiels-étapes plus connu sous le nom de graphes PERT (Programme

Evaluation and Research Task) est l’outil de résolution de ce type de problèmes ;

– Les flots dans les rÃľseaux : l’étude des circuits électriques, Kirchhof, qui a étudié

les réseaux électriques, peut être considéré comme un des précurseurs de cette

théorie ;

– La chimie, la sociologie et l’économie : la notion de clique est un exemple de

l’implication de la théorie des graphes dans ces disciplines.

5

Chapitre 1

Concepts fondamentaux des

graphes

1.1 Introduction

Les graphes représentent de manière simple et naturelle des relations entre les objets.

Les outils mathématiques et les algorithmes mises au point en théorie des graphes per-

mettent de résoudre une multitude de problèmes, tels que les problèmes de cheminement,

d’ordonnancement, d’affectation, etc.

1.1.1 Graphe orienté

Un graphe orienté G = (X, U) est défini par les deux ensembles :

– X = {x1, x2, . . . , xn} est l’ensemble fini de sommets, n > 1.

– U = {u1, u2, . . . , um} est l’ensemble fini d’arcs.

Chaque élément ui ∈ U est une paire ordonnée de sommets, ui = (x, y). x est

appelé extrémité initiale de ui et y est extrémité terminale.

U peut être vide.

1.1.2 Graphe non orienté

Un graphe non orienté G = (X, E) est défini par les deux ensembles :

– X = {x1, x2, . . . , xn} est l’ensemble fini de sommets, n > 1.

– E = {e1, e2, . . . , em} est l’ensemble fini d’arêtes.

Chaque élément ei ∈ E est une paire non ordonnée de sommets, ei = (x, y). x et

6

Concepts fondamentaux des graphes

y sont appelés extrémités de ei.

E peut être vide.

Les sommets représentent les objets et les arcs ou les arêtes représentent les liens

entre les différents objets.

1.1.3 Représentation graphique

On représente généralement un sommet par un point ou par un cercle. Un arc est

représenté par une flèche et une arête par un trait qui peuvent être courbés.

x6 x5

x1

x4

x2

x3

Figure 1.1 – Un graphe orienté

x1

x2

x3

x4

x5

Figure 1.2 – Un graphe non orienté

1.2 Définitions

– Le nombre de sommets dans un graphe est appelé l’ordre du graphe.

– Si les deux extrémités d’un arc (resp. d’une arête) sont confondues alors cet arc

(resp. cette arête) est appelée boucle.

– Si deux arcs (resp. deux arêtes) possèdent les mêmes extrémités, on dit alors qu’ils

sont parallèles.

Soit un arc u=(x, y) (resp. un arête e = {x, y}) :

– x et y sont dits sommets adjacents.

7


– Pour le cas de l’arc u : x est dit prédécesseur de y. y est dit successeur de x.

– x et y sont incidents à l’arc u (resp. à l’arête e), l’arc u (resp. l’arête e) est aussi

incident(e) aux sommets x et y.

– Deux arcs (resp. arêtes) sont dits adjacents s’ils ont une extrémité en commun.

Soit x ∈ X, un sommet du graphe orienté G = (X, U). On définit :

– Γ+(x) = Succ(x) = {y ∈ X/(x, y) ∈ U} appelé ensemble des successeurs de x.

– Γ−(x) = Pred(x) = {y ∈ X/(y, x) ∈ U} appelé ensemble des prédécesseurs

de x.

Soit x ∈ X, un sommet du graphe G, on appelle voisin de x tout sommet y ∈ X

différent de x et qui est adjacent à x. Ainsi, on définit l’ensemble V comme suit :

– V (x) = {y ∈ X − {x}/{x, y} ∈ E} pour les graphes non orientés.

– V (x) = V +(x) ∪ V −(x) où V +(x) = {y ∈ X − {x}/(x, y) ∈ U} et V −(x) = {y ∈

X−{x}/(y, x) ∈ U}.

– V +(x) (resp. V −(x)) est appelé ensemble des voisins externes (resp. internes) de

x.

Pour tout graphe orienté, on définit deux applications donnant l’extrémité initiale et

terminale d’un arc donné :

I : U → X, u = (x, y)→ x

T : U → X, u = (x, y)→ y

On appelle multiplicité d’un arc (resp. arête) (xi, xj), la valeur mij correspondant

au nombre d’arcs qui relient xi à xj. La multiplicité d’un graphe G est le nombre m(G)

correspondant au maximum des mij.

Un graphe orienté est dit p-graphe si m(G) = p.

Définition 1 (Graphe Simple) Un graphe non orienté est dit simple s’il ne contient

pas de boucles, de plus entre tout couple de sommets il y a au plus une arête.

Dans le cas d’un graphe G = (X, U) orineté, G est dit simple s’il ne contient pas de

boucles et entre tout couple de sommets x, y ∈ X il y a au plus un arc ayant x comme

extrémité initiale et y comme extrémité terminale.

8


1.3 Notion de degré

Définition 2 Soit G = (X, E) un graphe non orienté (resp. G = (X, U) un graphe

orienté). A tout sommet x ∈ X, on peut associer une valeur entière positive ou nulle,

notée dG(x), qu’on appelle degré du sommet x. Cette valeur est définie comme suit :

dG(x) = nombre de fois où x est extrémité d’un arc (resp. d’une arête).

Définition 3 Soit G = (X, U) un graphe orienté.

On appelle demi-degré extérieur d’un sommet x ∈ X, la valeur suivante :

d+G(x) = |{u ∈ U/I(u) = x}|

On appelle demi-degré intérieur d’un sommet x ∈ X, la valeur suivante :

d−

G(x) = |{u ∈ U/T (u) = x}|

Le degré d’un sommet x : dG(x) = d+G(x) + d−

G(x)

Remarque Pour tout graphe, nous avons : dG(x) > |V (x)|. Si G est un graphe non

orienté simple alors on a : dG(x) = |V (x)|.

Notations

– On appelle degré minimal d’un graphe G qu’on note par δ(G), le plus petit degré

dans le graphe G. δ(G) = min{dG(x)}

– On appelle degré maximal d’un graphe G qu’on note par ∆(G), le plus grand degré

dans le graphe G. ∆(G) = max{dG(x)}

– Si dG(x) = 0 Alors x est dit sommet isolé.

– Si dG(x) = 1 Alors x est dit sommet pendant.

– Un arc (resp. Une arête) incident(e) à un sommet pendant est aussi dit(e) arc

(arête) pendant(e).

1.3.1 Formule des degrés

Cas non orienté :

Pour tout graphe non orienté G = (X, E), on a :

∑

x∈X

dG(x) = 2|E|

9


preuve Chaque arête a exactement deux extrémité ⇒ Elle est comptée deux fois

dans le degré de chaque sommet ⇒ La somme totale des degrés est égale à deux fois le

nombre total d’arêtes.

Cas orienté :

Pour tout graphe orienté G = (X, U), on a :

∑

x∈X

dG(x) = 2|U | et∑

x∈X

d+G(x) =

∑

x∈X

d−

G(x) = |U |

Preuve Chaque arc a exactement une extrémité initiale et une extrémité termi-

nale ⇒ Chaque arc est comptabilisé une fois dans d+ pour son extrémité initiale et une

autre fois dans d− pour son extrémité finale. Le nombre total d’arcs ayant une extrémité

initiale (resp. terminale) est exactement la somme des demi-degrés extérieurs (resp. in-

térieurs).

Conséquence : De là, on peut déduire que le nombre de sommets de degrés impairs

dans un graphe est toujours pair.

1.4 Représentation machine

1.4.1 Matrice d’adjacence

A tout graphe d’ordre n on associe une matrice M de n lignes et n colonnes dont les

éléments sont notés Mij.

Pour un graphe non orienté G = (X, E),

Mij =

1 si xixj ∈ E

0 sinon(1.1)

Remarque 1

– La matrice d’adjacence M d’un graphe non orienté est toujours symétrique.

– La somme d’une ligne k = la somme d’une colonne k = dG(k). La boucle est

comptée deux fois.

Pour un graphe orienté G = (X, U), Mij représente le nombre d’arcs ayant i comme

extrémité initiale et j comme extrémité terminale.

10


M =

0 1 0 1 1

1 1 0 0 0

0 0 0 1 1

1 0 1 0 1

1 0 1 1 0

Figure 1.3 – Matrice d’adjacence du graphe non orienté de la figure 1.1

M =

0 0 0 0 0 1

0 0 0 0 1 1

0 1 0 1 0 1

0 1 0 1 0 0

0 0 0 0 0 0

0 0 0 0 1 0

Figure 1.4 – Matrice d’adjacence du graphe orienté de la figure 1.2

Remarque 2

– Les coefficients de M pour un graphe simple est binaire avec la diagonale com-

plètement à 0.

– La somme d’une ligne i = d+G(i). La somme d’une colonne j = d−

G(j).

1.4.2 Matrice d’incidence

A tout graphe non orienté G = (X, E), on peut associer une matrice M de n lignes

et m colonnes. Où n est le nombre de sommets dans G et m est le nombre d’arêtes dans

G.

Mij représente le nombre de fois où le sommet i est incident à l’arête j. Les éléments de

M sont dans {0, 1, 2}

Si deux colonnes j1 et j2 sont identiques alors les arêtes j1 et j2 sont parallèles.

Si un élément Mij = 2 alors l’arête j est une boucle.

A tout graphe orienté G = (X, U), on peut associer une matrice M de n lignes et m

colonnes. Où n est le nombre de sommets dans G et m est le nombre d’arcs dans G.

Une colonne nulle représente une boucle. Dans ce cas, toute boucle dans le graphe

11


est détectée mais son emplacement ne peut pas être précisé à partir de cette matrice.

1.4.3 Listes

A tout graphe orienté G=(X, U) avec |X| = n et |U | = m, on peut associer deux

tableaux (vecteurs) PS et LS : PS : tableau de pointeurs à n+1 éléments, où : PS[i] :

pointe sur la case contenant le premier successeur du sommet i dans LS.

On pose PS[1] = 1.

On pose pour tout n > i > 2 : PS[i] = k, où k = PS[i − 1]+ nombre de successeurs de

i-1

On pose PS[n + 1] = m + 1

Si un sommet i n’a pas de successeur, on aura PS[i] = PS[i + 1] LS : tableau de m

éléments, où :

Les successeurs d’un sommet i se trouvent entre la case numéro PS[i] et la case PS[i+1]-1

du tableau LS.

PS1 2 3 4 5 6 7

1 2 4 7 9 9 10

LS1 2 3 4 5 6 7 8 9

6 5 6 2 4 6 2 4 5

Figure 1.5 – Représentation par les listes de successeurs du graphe de la fig. 1.1

1.5 Graphes particuliers

Soit G = (X, U) un graphe orienté (resp. G = (X, E) un graphe non orienté). Soit

A ∈ X un sous ensemble de sommets et V ∈ U (resp. V ∈ E).

1.5.1 Sous graphe

Un sous graphe de G engendré par l’ensemble de sommets A est le graphe :

GA = (A, UA)oùUA = {u ∈ U/I(u) ∈ A et T (u) ∈ A} dans le cas orienté.

GA = (A, EA)oùEA = {e = {x, y} ∈ E/x ∈ A et y ∈ A} dans le cas non orienté.

12


1.5.2 Graphe partiel

Un graphe partiel de G engendré par l’ensemble d’arcs (resp. d’arêtes ) V est le

graphe GV = (X, V ).

1.5.3 Sous graphe partiel

Un sous graphe partiel de G engendré par l’ensemble de sommets A et l’ensemble

d’arcs (resp. d’arêtes) V est le graphe GA,V = (A, VA).

VA est l’ensemble d’arcs (resp. arêtes) qui one leurs deux extrémités dans le sous ensemble

V.

1.5.4 Complément d’un graphe

Le graphe complémentaire de G est noté G = (X, U ) (resp. = (X, E)) où :

U = {(x, y) ∈ X2/(x, y) /∈ U}(resp. = {{x, y} ∈ X2/{x, y} /∈ E}

1.6 Propriétés des graphes

1.6.1 Graphe Simple

Un graphe est dit simple s’il ne contient ni boucles ni arcs parallèles. Si G est simple,

on a dG(x) = |V (x)|.

1.6.2 Graphe Complet

Dans le cas orienté : G est complet ssi ∀x, y ∈ X, (x, y) /∈ U ⇒ (y, x) ∈ U Dans le

cas non orienté : G est complet ssi ∀x 6= y ∈ X, {x, y} ∈ E. Un graphe simple complet

d’ordre n est noté Kn.

x6 x5

x1

x4

x2x3

Figure 1.6 – Un graphe complet

13


1.6.3 Graphe Régulier

Un graphe G est dit k-régulier si ∀x sommet de G, on a dG(x) = k. En d’autres

termes, δ(G) = ∆(G) = k.

x6 x5

x1

x4

x2x3

Figure 1.7 – Un graphe régulier

1.6.4 Graphe Symétrique

Cette notion est spécifique aux graphes orientés. G est symétrique ssi ∀x, y ∈ X, (x, y) ∈

U ⇒ (y, x) ∈ U

1.6.5 Graphe Antisymétrique

Cette notion est spécifique aux graphes orientés. G est antisymétrique ssi ∀x, y ∈

X, (x, y) ∈ U ⇒ (y, x) /∈ U

1.6.6 Graphe Transitif

Cette notion est spécifique aux graphes orientés. G est transitif ssi ∀x, y, z ∈ X, (x, y) ∈

U et (y, z) ∈ U ⇒ (x, z) ∈ U

1.6.7 Graphe Biparti

G est dit biparti ssi l’ensemble de ses sommets X admet une partition en 2 sous

ensembles X1 et X2 avec X1 ∩X2 = ∅ et X1 ∪X2 = X.

Dans le cas orienté : ∀(x, y) ∈ U ⇒ x ∈ X1 et y ∈ X2

Dans le cas non orienté : ∀x, y ∈ E(x ∈ X1 et y ∈ X2)ou(x ∈ X2ety ∈ X1).

G est dit biparti complet ssi G est dit biparti et ∀x ∈ X1 et ∀y ∈ X2 ⇒ (x, y) ∈ U .

14


x4

x3

x2

x1

y3

y2

y1

Figure 1.8 – Un graphe biparti

Un graphe biparti complet et simple G = (X1∪X2, U) (resp. G = (X1∪X2, E)) avec

|X1| = p et |X2| = q est noté Kp,q.

1.6.8 Graphe Multiparti

G est dit multiparti ssi l’ensemble de ses sommets X admet une partition en p sous

ensembles X1, X2, . . . Xp (p > 3). Avec Xi ∩Xj = ∅(i 6= j) et X1 ∪X2 . . . ∪Xp = X.

Dans le cas orienté : ∀(x, y) ∈ U ⇒ x ∈ Xk et y ∈ Xk+1(avec1 6 k 6 p− 1).

Dans le cas non orienté : ∀x, y ∈ E(x ∈ Xk et y ∈ Xk + 1) ou (y ∈ Xk et x ∈

Xk+1)avec1 6 k 6 p− 1

1.7 Stable / Clique

On appelle stable dans un graphe G un sous-ensemble de sommets S ⊆ X et le sous

graphe engendré par S est formé de sommets isolés (ne contient aucun arc ou arête).

Dans le graphe de la figure 1.2 :

L’ensemble de sommet s = {x1, x3} est un stable.

L’ensemble de sommet s′ = {x2, x4} est un autre stable.

Chaque partition d’un graphe biparti est un stable.

On appelle clique dans un graphe G un sous-ensemble de sommets C ⊆ X où le sous

graphe engendré par C est un graphe complet.

L’ensemble de sommet {x1, x4, x5} est une clique.

Si S est le plus grand stable dans G Alors |S| 6 nombre de cliques dans G et |S| =

nombre minimal de cliques dans G.

15


Si C est la plus grande clique dans G Alors |C| 6 nombre de stables dans G et |C| =

nombre minimal de stables dans G.

1.8 Exploration d’un graphe

Beaucoup de problèmes sur les graphes nécessitent que l’on parcourt l’ensemble des

sommets et des arcs/arêtes du graphe.

Pour explorer un graphe depuis le sommet s, nous allons utiliser un algorithme basé

sur une opération de marquage.

Au départ tous les sommets sont non marqués, à l’exception du sommet de départ,

s. A chaque étape nous sélectionnons un sommet non marqué, adjacent à un sommet

déjà marqué, et nous le marquons à son tour.

Algorithme Exploration

Entrées Graphe G=(V,E), Sommet s

M : structure de données ordonnée

Initialiser tous les sommets à non marqué ; Marquer s ;

M ← s ;

Tant Que M 6= ∅

choisir un sommet x de M ;

Marquer x ;

M ←M \ {x} ; // Retirer x de l’ensemble M

Pour chaque voisin y non marqué de x

M ←M ∪ {y} ; // Ajouter y à l’ensemble M

Fin Pour

Fin TantQue

Il existe deux grandes stratégies "opposées" pour sélectionner à chaque étape le som-

met à marquer :

1. La recherche en profondeur DFS (Depth First Search)

Dans l’exploration, l’algorithme cherche à aller très vite "profondément" dans le

graphe, en s’éloignant du sommet s de départ. La recherche sélectionne à chaque

étape un sommet voisin du sommet marqué à l’étape précédente. Dans cette explo-

ration, M est une pile et la procédure choisir consiste donc à dépiler un sommet

16


(LIFO).

2. La recherche en largeur BFS (Breath First Search).

Dans l’exploration l’algorithme cherche au contraire à épuiser la liste des sommets

proches de s avant de poursuivre l’exploration du graphe (FIFO).

1.9 Isomorphisme

Définition 4 Soient deux graphes orientés G1 = (X1, U1) et G2 = (X2, U2). On dit que

G1 et G2 sont isomorphes (on note G1 ≡ G2) ssi ∃f : X1 → X2 et ∃g : U1 → U2 deux

bijections telles que ∀u ∈ U1, u = (x, y)⇔ g(u) = (f(x), f(y)).

Définition 5 Soient deux graphes non orientés G1 = (X1, E1)etG2 = (X2, E2). On dit

que G1 et G2 sont isomorphes (on note G1 ≡ G2) ssi ∃ϕ : X1 → X2 une bijection telle

que ∀x, y ∈ X1, e = x, y ∈ E1 ⇒ ϕ(x), ϕ(y) ∈ E2.

Figure 1.9 – Deux graphes isomorphes

Proposition 1 Soient deux graphes isomorphes G1 = (X1, U1) ≡ G2 = (X2, U2) (resp.

G1 = (X1, E1) ≡ G2 = (X2, E2)) alors |X1| = |X2| et |U1| = |U2| (resp. |E1| = |E2|) et

∀x ∈ X1 de degré dG1(x),∃y ∈ X2 de degré dG2(y) = dG1

(x).

Remarque 3 La réciproque n’est pas toujours vraie. On peut trouver deux graphes non

isomorphes ayant le même nombre de sommets et le même nombre d’arc (ou arêtes).

17

Chapitre 2

Cheminement dans les Graphes

2.1 Chaînes / Chemins

2.1.1 Chaîne

On appelle chaîne dans un graphe non orienté (resp. orienté) G = (X, E) (resp.

G = (X, U)), une suite alternée de sommets et d’arêtes (resp. d’arcs) :

µ = x0e1x1 . . . xk−1ekxk (resp. µ = x0u1x1 . . . xk−1ukxk) Tel que pour tout 1 6 i 6 k, xi

et xi+1 sont extrémités de l’arête ei (resp. de l’arc ui).

On dit que µ est une chaîne joignant les sommets x0 et xk de longueur k.

x1

x2

x3

x4

x5

e6

e5

e3

e2

e1

e4

e7

Figure 2.1 – Un graphe non orienté

C1 = x1e2x4e5x3e6x5 est une chaine de longueur 3

2.1.2 Chemin

On appelle chemin dans un graphe orienté G = (X, U), une suite alternée de som-

mets et d’arcs :

γ = x0u1x1 . . . xk−1ukxk Tel que pour tout 1 6 i 6 k, le sommet xi est extrémité initiale

de l’arc ui et le sommet xi+1 est son extrémité terminale.

18


x6 x5

x1

x4

x2

x3

u5

u3

u1

u4

u2

u7

u6

u8

u9

Figure 2.2 – Un graphe orienté

On dit que γ est un chemin de x0 vers xk de longueur k.

C2 = x3u6x2u5x5u3x6 est une chemin de longueur 3

C3 = x3u7x4u9x4u8x2u2x6 est une chemin de longueur 4

C4 = x1u1x6u2x2u6x3u7x4 est une chaine de longueur 4

2.1.3 Chaîne / Chemin simple

On dit qu’un chemin ou une chaîne est simple si tous les arcs ou les arêtes les

composants sont distincts.

2.1.4 Chaîne / Chemin élémentaire

On dit qu’un chemin ou une chaîne est élémentaire si tous les sommets les composants

sont distincts.

Remarque 4

- Toute chaîne (ou chemin) élémentaire est aussi simple. L’inverse n’est pas toujours

vrai.

- Dans un graphe simple, une chaîne ou un chemin peuvent être déterminés juste en

énumérant la suite des sommets qui les composent.

19


2.2 Cycles / Circuits

2.2.1 Chaîne fermée / Chemin fermé

Un chemin (resp. chaîne) dont les extrémités sont confondues est dit chemin fermé

(resp. chaîne fermée).

2.2.2 Cycle

On appelle cycle dans un graphe non orienté (resp. orienté) G = (X, E) (resp. G =

(X, U) ), toute chaîne fermée simple : µ = x0e1x1 . . . xk−1ekxk (resp. µ = x0u1x1 . . . xk−1ukxk)

Tel que k 0, et x0 = xk. On dit que µ est un cycle longueur k.

Proposition 2 Soit G = (X, E) un graphe si le degré minimum δ(G) ≥ 2 alors G

contient un cycle. Si G est simple et δ(G) ≥ k ≥ 2 alors G comporte un cycle de

longueur k.

2.2.3 Représentation vectorielle d’un cycle

Soit G=(X,U) un graphe avec |U| = m. On définit un sens de parcours arbitraire de

G.

Le vecteur µ de m éléments permet de représenter un cycle µ comme suit : chaque

élément du vecteur µ correspond à un arc ui ∈ U .

µi =

1 si ui fait partie du cycle dans le sens du parcours

−1 si ui fait partie du cycle dans le sens contraire du parcours

0 si ui /∈ µ

2.2.4 Circuit

On appelle circuit dans un graphe orienté G=(X, U), tout chemin fermé simple :

γ = x0u1x1 . . . xk−1ukxk tel que k > 0, et x0 = xk. On dit que γ est un circuit de

longueur k.

Définition 6 On dit qu’un cycle ou circuit est élémentaire si tous les sommets qui les

composent sont distincts.

Remarques La longueur d’un cycle ou d’un circuit est aussi égale au nombre de som-

mets formant ce cycle ou circuit.

20


Dans un graphe simple, un cycle ou un circuit peuvent être déterminés juste en

énumérant la suite des sommets qui les composent.

Une boucle est un cycle (circuit) élémentaire de longueur 1.

2.3 Connexité

Un graphe est dit connexe s’il existe une chaîne joignant chaque paire de sommets x

et y (x 6= y).

2.4 Composante connexe

Soit un graphe G = (X, E) (resp. G = (X, U)) :

Le sous graphe engendré par un sommet isolé est considéré comme une composante

connexe de G.

Si le sous graphe engendré par un ensemble de sommets S ⊆ X (GS) est connexe et le

sous graphe engendré par S∪x et x /∈ S n’est pas connexe Alors GS est une composante

connexe de G.

Remarque 5 Un graphe qui contient une seule composante connexe est dit graphe con-

nexe.

Proposition 3 Soit G Un graphe, l’ajout d’une arête a pour conséquence :

– soit dimininuer le nombre de composantes connexes.

– soit créer un nouveau cycle dans le graphe

Proposition 4 Un graphe G d’ordre n connexe comporte au moins n− 1 arêtes.

2.4.1 Graphe k-connexe

Un graphe G est dit k-connexe si et seulement si G est connexe d’ordre n > k + 1

et il n’existe pas d’ensemble S ⊂ X de cardinal k − 1 tel que le sous graphe engendré

par X − S n’est pas connexe.

En d’autres termes, en supprimant moins de k sommets, le graphe sera toujours connexe.

21


2.5 Forte Connexité

Définition 7 Un graphe orienté G=(X, U) est fortement connexe (f.c.) s’il existe entre

chaque paire de sommets x et y ∈ X (x 6= y) un chemin de x à y (xσy) et un chemin

de y à x (yρx).

2.5.1 Composantes fortement connexes (C.F.C.)

Soit G=(X, U) un graphe orienté :

Si le sous graphe engendré par un ensemble de sommets S ⊂ X (GS) est fortement

connexe et le sous graphe engendré par S∪x et x /∈ S n’est pas fortement connexe Alors

GS est une composante fortement connexe de G.

2.6 Algorithmes de calcul des composantes fortement con-

nexes

Soit G = (X, U) un graphe orienté, On définit pour chaque sommet x ∈ X deux

ensembles :

– L’ensemble des descendants de x : D(x) = {y ∈ X/xσy}

– L’ensemble des ascendants de x : A(x) = {y ∈ X/yσx}

Principe : A partir d’un sommet r, on calcule la c.f.c. à laquelle appartient r.

– On calcule l’ensemble des descendants de r (noté D).

– On calcule l’ensemble des ascendants de r (noté A).

– c.f.c. est {r} ∪A ∩D.

Données :

– En entrée :

– X : ensemble de n éléments représentant les identificateurs des sommets.

– U : ensemble de m éléments sous forme (i, j) représentant les arcs où i, j ∈ X

– r : identificateur d’un sommet de X qu’on appelle racine.

– En sortie :

– CFC : sous-ensemble de X. Le sous graphe engendré par cet ensemble représente

une composante fortement connexe.

– Autres :

22


– i, j : variables sommets.

– Marque : vecteur de n éléments booléens.

– A, D : sous-ensembles de X. Ils représentant l’ensemble des ascendants et

l’ensemble des descendants de la racine.

L’algorithme :

(* Initialisation *)

D ← {r} ;

Pour tout i ∈ X Marque[i]← faux ;

(* Recherche des descendants de r *)

Tant que (∃i ∈ D)

Marque[i]← vrai ;

Pour tout (i, j) ∈ U D ← D ∪ {j} ;

(* Réinitialisation *)

A← {r} ;

Pour tout i ∈ X Marque[i]àfaux ;

(* Recherche des ascendants de r *)

Tant que (∃i ∈ A) et (Marque[i] = faux)

Marque[i]← vrai

Pour tout (j, i) ∈ U A← A ∪ {j} ;

(* Calcul de la C.F.C. *)

CFC ← D ∩A ;

2.6.1 Graphe réduit

A tout graphe orienté G = (X, U) on associe le graphe simple GR = (XR, UR) appelé

graphe réduit de G défini comme suit :

XR = {A chaque c.f.c. Ci de G correspond un sommet Ci}

UR = {(Ci, Cj)/i 6= j et ∃x ∈ Ci et ∃y ∈ Cj et (x, y) ∈ U}

Remarque 6 Un graphe fortement connexe possède une seule C.F.C. Le graphe réduit

d’un graphe ne possède pas de circuits.

23


2.7 Cocycles et Cocircuits

Définition 8

Soit G = (X, E) un graphe non orienté, soit S ∈ X :

On appelle cocycle dans G associé à S, l’ensemble d’arêtes (noté ω(S)) ayant exactement

une extrémité dans S.

ω(S) = {e = {x, y} ∈ E/(x ∈ Sety /∈ S) ou (x /∈ Sety ∈ S)}

Définition 9

Soit G = (X, U) un graphe orienté, soit S ⊂ X, On note par :

ω+(S) = {u = (x, y) ∈ U/x ∈ S et y /∈ S}

ω−(S) = {u = (x, y) ∈ U/x /∈ S et y ∈ S}

ω(S) = ω+(S) ∪ ω−(S)

On appelle l’ensemble d’arcs ω(S) cocycle dans G associé à S.

Définition 10 Cocircuit

Un cocircuit dans un graphe orienté G = (X, U) est un cocycle dans G, dans lequel tous

les arcs sont orientés dans le même sens.

Définition 11

Un ensemble d’arcs θ ⊂ U est un cocircuit si ∃S ⊂ X/θ = ω(S)et(ω+(S) = ∅ ou

ω−(S) = ∅)

Proposition 5

Un graphe G = (X, U) est fortement connexe si et seulement si ∀S ⊂ X, on a ω+(S) 6= ∅

(resp. ω−(S) 6= ∅)

2.7.1 Représentation vectorielle d’un cocycle

Soit G = (X, U) un graphe avec |U | = m. Le vecteur θ de m éléments permet de

représenter un cocycle θ = ω(S) = ω+(S) ∪ ω−(S) comme suit : chaque élément ωi du

vecteur ω correspond à un arc ui ∈ U

θi =

1 si ui ∈ ω+(S)

−1 si ui ∈ ω−(S)

0 si ui /∈ ω(S)

24


2.8 Parcours Eulériens

Définition 12

Un parcours Eulerien passe une fois et une seule fois par chaque arête (resp. arc) du

graphe. Le parcours peut être une chaîne, un chemin, un cycle ou un circuit. Soit G un

graphe contenant m arêtes (resp. m arcs) :

Une chaîne simple, un chemin simple, un cycle simple ou un circuit simple de longueur

m est appelé Eulérien.

Théorème 1 Euler 1766

Un multigraphe G admet une chaîne Eulérienne si et seulement si il est connexe (à des

points isolés près) et le nombre de sommets de degré impair est 0 ou 2.

Conséquences Un graphe G admet une chaîne Eulérienne d’un sommet x à un som-

met y (x 6= y) si et seulement si dG(x) et dG(y) sont impairs et ∀z sommet de G (z 6= x

et z 6= y), on a dG(z) pair.

Un graphe G admet un cycle Eulérien si et seulement ∀x sommet de G, on a dG(x) pair.

Proposition 6

Un graphe G = (X, U) admet un circuit Eulérien si et seulement si pour tout sommet

x, on a d+G(x) = d−

G(x). (On dit que G est pseudo-symétrique)

2.9 Parcours Hamiltoniens

Définition 13

Un parcours Hamiltonien passe une fois et une seule fois par chaque sommet du graphe.

Le parcours peut être une chaîne, un chemin, un cycle ou un circuit. Soit G un graphe

d’ordre n (contenant n sommets) : Une chaîne (resp. un chemin) élémentaire de longueur

n− 1 est appelé chaîne Hamiltonienne (resp. chemin Hamiltonien).

Un cycle (resp. circuit) élémentaire de longueur n est appelé cycle (resp. circuit) Hamil-

tonien.

Théorème 2

25


Le théorème ci-dessous est utilisé pour démontrer qu’un graphe n’est pas Hamiltonien

(ne contient pas de cycle Hamiltonien).

Si G = (X, E) est un graphe Hamiltonien, alors pour tout ensemble de sommets S ⊂ X,

on a : p(GX−S) 6 |S| où p(GX−S) est le nombre de composantes connexes du sous

graphe de G induit par l’ensemble X − S.

26

Chapitre 3

Problèmes de cheminement dans

les Graphes

Les problèmes de cheminement dans les graphes, en particulier la recherche du plus

court chemin, comptent parmi les problèmes les plus anciens de la théorie des graphes

et les plus importants par leurs applications : coût de transport, temps de parcours,

problème de trafic,. . . Les algorithmes de recherche de plus court chemin seront différents

selon les caractérisitiques du graphe.

3.1 Graphes sans circuits

Les propositions suivantes caractérisent les graphes sans circuits :

Proposition 7 Un graphe orienté G = (X, U) est dit sans circuits si et seulement si

toute composante fortement connexe est réduite à un sommet.

Proposition 8 Un graphe orienté G = (X, U) est dit sans circuits si et seulement si il

est isomorphe à son graphe réduit.

Proposition 9 Un graphe orienté G = (X, U) est dit sans circuits si et seulement si

tout chemin dans G est élémentaire.

3.1.1 Source et Puits

Un sommet s est appelé source si et seulement si d−(s) = 0.

Un sommet p est appelé puits si et seulement si d+(p) = 0.

27

Problèmes de cheminement dans les Graphes

Tout graphe sans circuits possède une source et un puits.

Proposition 10 Dans un graphe sans circuits G = (X, U) ∀x ∈ X, l’extrémité initiale

(s ∈ X) d’un plus long chemin vers x est une source.

Proposition 11 Dans un graphe sans circuit G = (X, U) ∀x ∈ X, l’extrémité terminale

(p ∈ X) d’un plus long chemin commençant en x est un puits.

3.2 Partition en niveaux d’un graphe sans circuits

3.2.1 Niveau d’un sommet

Soit G = (X, U), un graphe orienté sans circuits. A tout x ∈ X, on associe deux

entiers :

v(x) : niveau du sommet x et représente la longueur maximale d’un chemin élémentaire

se terminant à x. On affecte par convention à une source s la valeur v(s) = 0.

Soit G = (X, U) un graphe orienté, et soit λ(G) la longueur du plus long chemin élé-

mentaire dans G, λ(G) = maxx∈X{v(x)}.

3.2.2 Partition en niveaux

Soit G = (X, U) est un graphe sans circuits. L’ensemble des sommets X peut être

partitionné au maximum en λ(G) + 1 stables. Où chaque sommet de niveau i sera placé

dans le stable Ni. Chaque stable Ni représente un niveau de G.

Proposition 12 G=(X,U) est un graphe sans circuits si et seulement si X admet une

partition {N0 ∪N1 ∪ . . . ∪Np} tel que x ∈ Ni ⇔ v(x) = i

3.3 Graphe pondéré (Réseau)

Soit G=(X,U) un graphe orienté, On définit p : U −→ R une application qui associe

pour chaque arc u ∈ U de G une valeur réelle p(u) appelée poids de l’arc u. Un tel graphe,

représenté par G = (X, U, p), est appelé graphe pondéré, graphe valué ou réseau.

3.3.1 Poids d’un chemin

On définit le poids d’un chemin γ comme la somme des poids des arcs de γ, p(γ) =∑

u∈γ

p(u). On l’appelle aussi distance.

28


3.3.2 Circuit absorbant

Un circuit γ est dit absorbant si son poids est négatif (p(γ) < 0).

3.4 Algorithme de Bellman-Ford

A chaque sommet x ∈ X, on veut associer un chemin de poids optimal joignant la

source du graphe r ∈ X à x dans le réseau R = (X, U, p)

3.4.1 Principe

L’algorithme consiste à affecter à chaque sommet x ∈ X d’un réseau R = (X, U, p)

sans circuits, une valeur π(x) (appelée potentiel de x) qui représente le poids du chemin

optimal reliant r à x. Il se base sur la liste des prédécesseurs de chaque sommet.

3.4.2 Les données

En entrée

X : ensemble des sommets

U : ensemble d’arcs sous forme (x,y)

p : un vecteur de n éléments où p[i] représente le poids du sommet i dans le réseau.

r : un sommet donné de X.

En sortie

π : vecteur de n éléments. π(x) représente le poids du chemin optimal de r vers x

S : ensemble des sommets qui sont extrémité terminale d’un chemin commençant par r

et pour lesquels π(i) est calculé définitivement.

3.4.3 Algorithme

Debut

S ← {r}

Pour tout x ∈ X ; π(x)← +∞ ; Pré(x)← NULL ; π(r)← 0

Pour tout (x ∈ S) et (∀u ∈ U avec T (u) = x on a I(u) ∈ S) Faire

Pour tout ((x, y) ∈ U) Faire

Si π(x) > π(y) + p(u) Alors π(x)← π(y) + p(u) ; Pré(x)← y

Fait

29


S ← S \ x

Fait

Fin

Remarque 7

Si le chemin optimal est le chemin de poids maximal, on change dans l’algorithme min

par max et +∞ par −∞

Si ∀x ∈ X p(x) = 1, l’algorithme calculera le plus court chemin en nombre d’arcs.

La complexité de l’algorithme est O(n2).

3.5 Algorithme de Dijkstra

Le problème est le même que celui traité par Bellman, sauf qu’ici le réseau R=(X,U,p)

peut être avec ou sans circuits mais à condition que les poids soient tous positifs ou nuls.

Le sommet de départ r n’est pas nécessairement une source.

Principe L’algorithme calcule le chemin de poids minimal en partant du sommet r

et en prolongeant le chemin à chaque itération. Cette méthode s’appelle, calcul de la

plus courte distance de proche en proche. A chaque étape, pour un sommet donné x, on

ajuste les valeurs π[y] pour tout sommet y successeur de x.

Les données

En entrée

X : ensemble des sommets

U : ensemble d’arcs sous forme (x, y)

p : un vecteur de n éléments où p[i] représente le poids de l’arc i dans le réseau.

r : un sommet donné de X.

En sortie

π : vecteur de n éléments. Chaque entrée π[x] représente le poids du chemin optimal de

r vers x

S : ensemble des sommets qui sont extrémité terminale d’un chemin commençant par r.

30


Autres

f : vecteur de n éléments. Chaque entrée f [k] contient un sommet de X. le vecteur f à

la fin sera trié dans un ordre croissant par rapport aux valeurs de π[f [k] ].

I(u) : donne l’extrémité initiale de l’arc u. T (u) : donne l’extrémité terminale de l’arc u.

3.5.1 L’Algorithme

Début

s← r ; k ← 1 ; f [k]← r

Pour tout x ∈ X faire π[x]← +∞ fait

π[r]← 0

Tant que (k < n) et (π[x] < +∞)

Faire

Pour tout u ∈ U/(I(u) = f [k]) et (T (u) /∈ S)

faire

x=T(u)

Si π(x) > π[f [k]] + p[u]

Alors π(x)← π[f [k]] + p[u] ; Pré(x)← f [k]

Fait

x← y/y ∈ X − S et π[y] minimal

k ← k + 1

f [k]← x

S ← S \ ∪x

Fait

Fin.

31

Chapitre 4

Problèmes d’ordonnancement

4.1 Introduction

On a affaire à un problème d’ordonnancement lorsque l’on est confronté à un prob-

lème d’organisation. Il faut accomplir de multiples tâches qui demandent un certain

temps d’exécution et qui doivent être exécutées dans un certain ordre. II est donc néces-

saire d’identifier les tâches prioritaires en fonction de l’objectif à atteindre et, lors de

leur exécution, il faut détecter les retards et les dépassements de moyens.

Un problème d’ordonnancement consiste alors à organiser dans le temps la réalisa-

tion de tâches d’un projet, compte tenu de contraintes temporelles (délais, contraintes

d’enchaînement) et de contraintes portant sur la disponibilité des ressources requises afin

de minimiser la durée globale du projet.

Les nombreuses méthodes d’ordonnancement peuvent se regrouper en deux grandes

familles selon le principe de base qu’elles utilisent. On distingue :

– les méthodes du type diagramme à barres : GANTT

– les méthodes à chemin critique : potentiel-tâches, potentielétapes (PERT).

4.2 contexte

Un projet consiste en un ensemble de n tâches liées par des contraintes de succession

ou de précédence, l’objectif est de :

– Calculer la durée minimale du projet.

– Déterminer les dates de début au plus tôt et au plus tard des tâches.

– Déterminer les tâches critiques.

32


Il faut donc identifier les tâches, leurs durées et les contraintes de succession ou de

précédence entre ces différentes tâches. Nous ne considérons pas les contraintes liées aux

ressources dans ce cours (les ressources sont supposées illimitées).

4.3 Les tâches

Une tâche est l’activité élémentaire caractérisée par :

– Sa durée di.

– Sa date de début ti et sa date de fin fi. La date de fin est égale à ti + di.

– Eventuellement les ressources nécessaires à son accomplissement.

Les tâches sont supposées non-préemptives : une fois que l’exécution a commencé, elles

se poursuit sans interruption jusqu’à la fin.

Il existe entre les tâches d’un projet des relations de précédence, qui signifient par

exemple qu’une tâche ne peut débuter que si certaines autres tâches sont finies.

4.4 Diagramme de Gantt

On peut représenter sur le graphique l’avancement des travaux. En effet on indique

par une barre le travail effectivement accompli depuis que les tâches ont été commencées.

Si on procède ainsi pour toutes les tâches on saura à tout moment quel est l’état réel

d’avancement du projet.

Considérons le problème d’ordonnancement suivant :

Tâches Durée Contraintes

a 6

b 3

c 6

d 2 b achevée

e 4 b achevée

f 3 a et d achevées

33


t

Tâches

1 2 3 4 5 6 7 8 9

a

b

c

d

e

f

Figure 4.1 – Diagramme de Gantt

4.5 Représentation par un graphe potentiels-tâches

On peut représenter un problème d’ordonnacement simple par une graphe orienté

G = (X, U) :

– Chacun des sommets de X represente une tâche.

– Les arcs U représente les contraintes de potentiels (de précédence en général) :

U = {(i, j) ∈ X ×X, ∃ une contrinte tj − ti 6 aij}

Le poids associé à un arc (i, j) est pij = aij .

– On ajoute à cela deux sommets α et ω representant les tâches fictives début et

fin de projet

Le graphe potentiels-tâches du problèmes précédent est donné ci-dessous.

α

a

b

c

d

e

f

ω0

0

0

6

3

3

23

4

6

Figure 4.2 – Le graphe Potentiels-Tâches

34


4.6 Recherche d’un ordonnancement optimale

La résolution d’un problème d’ordonnancement revient à déterminer le calendrier

optimal du projet, qui consiste en :

– La durée minimale du projet qui correspond à la date au plus tôt de fin du projet.

– Les dates au plus tôt de début de chaque tâche.

Théorème 3 Il existe un ordonnancement réalisable si et seulement si ∄ de circuit de

valeur strictement positive dans G.

Si la condistion d’existence est vérifiée alors, il existe en général un ordonnancement

réalisables de durée minimale.

La determination du calendrier optimal consiste à déterminer (tα, t1, t2, . . . , tn, tω) de

façon à :

Minimiser (tω − tα) sous les condistions :

1. Contraintes de potentiel : tj − ti > aij

2. Contraintes de non négativité : tα, t1, . . . , tn, tω > 0

Théorème 4 Dans le cas d’un graphe sans circuit, on a

t0 = 0, ti = maxj∈Γ−1(i)

(tj + vji)

vji est la valuation de l’arc (j, i) (par exemple la durée dj de j) Γ−1(i) est l’ensemble des

prédécesseurs de i.

La date de début au plus tôt ti d’une tâche i est égale à la longueur du

plus long chemin allant de α à i.

Dans l’exemple précédent, on peut voir que la durée minimale du projet est 9,

qui, correspond au plus long chemin allant de α à ω (αafω).

– Les dates au plus tôt ta, tb et tc des tâches a, b et c sont toutes égale à 0.

– Les dates au plus tôt td et te des tâches d et e sont égale à 3.

– La date au plus tôt tf de la tâche f est égale à 6.

On peut aussi déterminer les dates de début au plus tard des taches ti sans retarder

le projet, c-à-d que tω = tω

35


Théorème 5 Dans le cas d’un graphe sans circuit, on a

tω = tω, ti = minj∈Γ(i)

(tj + vij)

4.7 Marges totales et chemin critique

Définition 14 La marge totale d’une tâche i est le retard total qu’on peut se permettre

sur i sans remettre en cause la date de fin du projet.

Mi = ti − ti

Définition 15 Les tâches critiques ont une marge nulle, tout retard sur leur exécution

entraîne un retard global sur le projet.

Un chemin est critique s’il relie α et ω et s’il ne contient que des tâches critiques.

Définition 16 La marge libre d’une tâche i est le retard total qu’on peut se permettre

sur i sans remettre en cause la date de début des autres taâches.

mi = mink∈Γ(j)

(tk − ti − di)

36

Chapitre 5

Arbres et Arborescences

5.1 Introduction

Les arbres sont des graphes particuliers, très utilisés en algorithmiques et en infor-

matique.

Définition 17 Un arbre est un graphe connexe sans cycle. Une forêt est un graphe sans

cycle.

x1

x2

x3

x4 x5

Figure 5.1 – Un arbre

Il existe de nombreuses caractérisations pour les arbres :

– Si nous regardons la propriété de connexité, les arbres apparaîssent comme des

graphes connexes minimaux, au sens où retirer la moindre arête les déconnecte.

– Si nous regardons les arbres sous l’angle des graphes acycliques, ils sont maximaux,

au sens où ajouter la moindre arête crée un cycle.

37


Il existe également une relation très forte entre le nombre d’arêtes et le nombre de

sommets d’un arbre : un arbre T=(V,E) comporte exactement |V | − 1 arêtes. En effet :

– Un graphe connexe comporte au moins |V | − 1 arêtes.

– Un graphe sans cycle comporte au plus |V | − 1 arêtes.

Théorème 6 Pour un graphe T d’ordre n, il y a équivalence entre les propriétés :

1. T est un arbre

2. T est un graphe connexe à n-1 arêtes

3. T est connexe, et la suppression de toute arête le déconnecte

4. T est acyclique à n-1 arêtes

5. T est acyclique et l’ajout de toute arête le rend cyclique.

Preuve Pour montrer l’équivalence entre ces 5 propriétés, le plus simple est d’établir

une série d’implications.

(1) ⇒ (2) Le graphe T étant à la fois connexe et acyclique, il possède exactement

n− 1 arêtes. (cf propriété des graphes connexes et propriété des graphes acycliques).

(2) ⇒ (3) La suppression d’une arête de T donne un graphe à n − 2 arêtes : il ne

peut être connexe (cf propriété des graphes connexes).

(3)⇒ (4) Par l’absurde si T possèdait un cycle, la suppression d’une arête de ce cycle

ne saurait le déconnecter. Par suite T est acyclique. Puisqu’il est également connexe, il

possède donc exactement n-1 arêtes.

(4) ⇒ (5) L’ajout d’une arête à T donne un graphe à n arêtes : il ne peut être

acyclique (cf propriété des graphes acycliques).

(5)⇒ (1) Considérons 2 sommets x et y de T . Si il existe l’arête (x, y), alors c’est un

chemin de x à y. Sinon ajoutons cette arête à T : nous créons alors un cycle, de la forme

(x, a, . . . , z, y, x). Ceci montre l’existance du chemin (x, a, . . . , z, y) entre x et y dans T .

Par définition T est donc un graphe connexe.

5.2 L’arborescence

une arborescence est un arbre comportant un sommet particulier r, nommé racine de

l’arborescence à partir duquel il existe un chemin unique vers tous les autres sommets.

La racine ne possède pas de prédécesseurs, les arcs sont tous orientés de la racine

vers les feuilles. Les feuilles sont les sommets n’ayant pas de successeurs.

38


5.3 Arbre couvrant

Imaginons que nous ayons à connecter des villes entre elles, par exemple avec un

nouveau réseau électrique. Si on suppose qu’un certain nombre de connexions directes

point à point entre les villes sont possibles. Il nous faut choisir lesquelles parmi ces

connexions nous allons effectivement mettre en place. Les coûts d’installation du réseau

ne sont évidemment pas les mêmes. Nous aimerions donc déterminer comment connecter

toutes les villes en minimisant le coût total du réseau.

Ce problème en théorie des graphe correspond à la recherche d’un arbre couvrant

de poids minimum. L’ensemble des connexions potentielles peut être représenté par un

graphe G = (V, E) dans lequel chaque arête e est associée à un coût C(e) positif. Con-

necter toutes les villes correspond à sélectionner un ensemble d’arêtes F de G tel que

le graphe partiel H = (V, F ) induit est connexe. Le poids de cette solution C(H) est

définie comme la somme des poids de ses arêtes.

Notre problème s’énonce donc : Etant donné un graphe G = (V, E), déterminer un

graphe partiel connexe H = (V, F ) de poids minimum.

Il est facile de voir qu’un tel graphe partiel H doit être un arbre : si H n’est pas

acyclique, on peut supprimer une arête d’un de ses cycles sans le déconnecter et en

faisant diminuer le poids total.

Définition 18 Un arbre couvrant pour un graphe G = (V, E) est un arbre construit

uniquement à partir des arêtes de E et qui connecte ("couvre") tous les sommets de V .

Un arbre couvrant d’un graphe G est donc un graphe T tel que :

– Le graphe T est un arbre.

– Le graphe T est un graphe partiel de G.

5.4 Arbre couvrant de poids minimun

Le problème de l’arbre couvrant de poids minimum consiste à trouver un arbre

couvrant dont la somme des poids c(e) des arêtes est minimum.

La seule condition, nécessaire et suffisante, pour qu’un graphe admette un arbre

couvrant est qu’il soit connexe.

Il existe 2 algorithmes célèbres pour résoudre le problème de l’arbre couvrant de

poids minimum (MST, Minimum Spanning Tree) :

39


– Algorithme de Prim : Il maintient au fur et à mesure de la construction un

sous-graphe connexe qui grossit petit à petit.

– Algorithme de Kruskal Il maintient au fur et à mesure de la construction

un graphe partiel acyclique. Si les algorithmes de recherche sont spécifiques aux

graphes.

Nous présentons dans ce document seulement l’algorithme de Kruskal, qui se base

sur la caractérisation des arbres, étant des graphes acycliques maximaux.

L’algorithme consiste à ajouter au fur et à mesure des arêtes, en s’assurant que le graphe

partiel reste à chaque étape une forêt, jusqu’à ce que la forêt devienne un arbre.

Algorithme Kruskal

Entrées : Graphe G = (V, E), C une valuation positive des arêtes ;

Sorties : T = (V, F ) un arbre couvrant de poids minimum ;

A← E ;

F ← ∅ ;

i← 0 ;

Tant que i < |V | faire

Choisir e ∈ A de poids minimum ;

A← A− {e} ;

i← i + 1 ;

si T = (V, F ∪ {e}) est acyclique alors F ← F ∪ e ;

fait

Retourner T = (V, F ) ;

fin.

Si le graphe G est connexe, l’algorithme de Kruskal délivre bien sûr un arbre couvrant

de poids minimum. sinon il délivre une forêt maximale de point minimum.

La compléxité de l’algorithme de Kruskal est de O(Elog(E)).

40

Chapitre 6

Les flots

6.1 Introduction

Les flots permettent de modéliser une très large classe de problèmes. Leur interpréta-

tion correspond à la circulation de flux physiques sur un réseau : distribution électrique,

réseau d’adduction d’eau ou tout autre liquide, acheminement de paquets sur un réseau

informatique, ...

Il s’agit d’acheminer la plus grande quantité possible de matière entre une source s

et une destination t. Les liens permettant d’acheminer les flux ont une capacité limitée,

et il n’y a ni perte ni création de matière lors de l’acheminement : pour chaque noeud

intermédiaire du réseau, le flux entrant (ce qui arrive) doit être égal au flux sortant (ce

qui repart) (Conservation des flux en chaque sommet : loi de Kirchhoff).

Définition 19 (Les réseaux)

Un réseau est un graphe orienté R = (X, U) avec une valuation positive de ses arcs. La

valuation d’un arc (x, y), notée c(x, y), est appelée la capacité de l’arc.

On distingue sur un réseau R deux sommets particuliers : un sommet dit source s et

un autre dit destination t.

Les arcs de capacité nulle ne sont pas représentés sur le réseau.

41

Les flots

s

a

b

c

d

e

f

t4

7

5

6

3

3

24

5

4

4

3

Figure 6.1 – Un réseau

6.2 Flot

Un flot représente l’acheminement d’un flux, de matière par exemple, depuis une

source s vers une destination t.

Un flot vérifie la loi de conservation analogue aux lois de Kirshoff en électricité, c’est

à dire que le flux entrant à une nœud (ce qui arrive) doit être égal au flux sortant de ce

nœud (ce qui repart). Il n’est donc pas possible de stocker ou de produire de la matière

aux nœuds intermédiaires

Définition 20 (Le flot)

Un flot ϕ sur un réseau R = (X, U) est une valuation positive ϕ des arcs, ϕ est

une application définie de U dans ℜ+, telle que : pour tout sommet x ∈ U \ {s, t},∑

y ϕ(y, x) =∑

y ϕ(x, y)

Le flux transitant sur chacun des arcs du réseau doit être inférieure à la capacité de

cet arc (flot compatible ou admissible).

Un flot est dit compatible si pour tout arc (x, y) ∈ U , 0 ≤ ϕ(x, y) ≤ c(x, y).

La valeur du flot est définie comme le flux net sortant de s (∑

x ϕ(s, x)−∑

x ϕ(x, s))

ou entrant dans t (∑

x ϕ(x, t)−∑

x ϕ(t, x)) .

Définition 21 (Flot maximum)

Un flot maximum dans un réseau est un flot compatible de valeur maximale.

42

Les flots

6.3 Propriétés fondamentales

6.3.1 Flot maximal et coupe minimale

Dans un réseau de transport R = (X, U), soit S un sous-ensemble de X et T son

complément. Une coupe (s− t) se définit par une partition X = S ∪T des sommets telle

que s ∈ S et t ∈ T . Les arcs de la coupe sont alors les arcs (x,y) ayant leur extrémité

initiale dans S et leur extrémité terminale dans T .

La capacité d’une coupe, notée v(S, T ), est donnée par la somme des capacités

des arcs de la coupe.

v(S, T ) =∑

u∈ω+(S)

c(u)

Théorème 7 Ford-Fulkerson (Max-flow Min-cut)

La valeur d’un flot maximum ϕ dans le réseau R est égale à la plus petite des capacités

des coupes s− t.

6.3.2 Graphe d’écart et chemin augmentant

Soit ϕ un flot compatible sur R. Le graphe d’écart associé à ϕ sur R est le graphe

Re(ϕ) = (X, U e(ϕ)) défini comme suit : ∀u = (i, j) ∈ U ,

– Si ϕ(u) < c(u), (i, j) ∈ U e(ϕ) avec la capacité (résiduelle) c′(i, j) = c(u) − ϕ(u)

– Si ϕ(u) > 0, (j, i) ∈ A avec la capacité c′(j, i) = ϕ(u)

Soit ϕ un flot admissible sur R et Re(ϕ) = (X, U e(ϕ)) le graphe d’écart associé.

Soit µ un chemin allant de s à t dans Re(ϕ) et δ = minu∈µ c(u). Ce chemin est appelé

chemin augmentant car il est possible d’augmenter la valeur du flot sur R de δ de la

façon suivante ∀(i, j) ∈ µ :

– Si u = (i, j) ∈ U , alors ϕ(u) = ϕ(u) + δ

– Si u = (j, i) ∈ U , alors ϕ(u) = ϕ(u) − δ

Recherche d’un flot maximal : algorithme de Ford-Fulkerson Soit un réseau

R, un flot compatible ϕ dans R et le graphe décart Re(ϕ). Pour déterminer un flot

maximum, l’algorithme générique consiste, à chaque itération, à chercher un chemin µ

43

Les flots

allant de s à t dans Re(ϕ). Si un tel chemin existe, on augmente le flot ϕ de la quantité

δ = minu∈µ c′

u. Sinon l’algorithme termine et ϕ est le flot de valeur maximale.

s

a

b

c

d

e

f

t4

4

5

4

1

3

14

5

4

1

1

Figure 6.2 – Un flot

44

Les flots

7

45

Documents

Table des matières - perso.usthb.dzperso.usthb.dz/~mboukala/CoursTG.pdf · Introduction générale La théorie des graphes est un très vaste domaine, en évolution constante tant