TH Graphes

Ministère de l’Enseignement Supéieur et de la Recherche Scientifique
Université des Sciences et de la Technologie Houari Boumediene

Département Informatique
Support de Cours
Théorie des Graphes
Licence: L3
Contents
Introduction générale 7
1 Concepts fondamentaux des graphes 9

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.1 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.2 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.3 Représentation graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Notion de degré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Formule des degrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Propriétés des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.1 Graphe Simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.2 Graphe Complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.3 Graphe Régulier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.4 Graphe Biparti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Sous-graphes et graphe partiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5.1 Graphe partiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5.2 Sous graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5.3 Complément d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 Cliques et stables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 Représentation d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7.1 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7.2 Matrice d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7.3 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.8 Isomorphisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.9 Exploration d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.10 Chaînes / Chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.10.1 Chaîne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.10.2 Chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.10.3 Chaîne / Chemin simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.10.4 Chaîne / Chemin élémentaire . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.11 Cycles / Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.11.1 Chaîne fermée / Chemin fermé . . . . . . . . . . . . . . . . . . . . . . . . 20
1.11.2 Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.11.3 Représentation vectorielle d’un cycle . . . . . . . . . . . . . . . . . . . . . 20
1.11.4 Circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3
1.12 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.13 Composante connexe (cc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.13.1 Graphe k-connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.14 Forte Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.14.1 Composantes fortement connexes (cf c) . . . . . . . . . . . . . . . . . . . 21
1.15 Algorithmes de calcul des composantes fortement connexes . . . . . . . . . . . . 22
1.15.1 Graphe réduit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.16 Cocycles et Cocircuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.16.1 Représentation vectorielle d’un cocycle . . . . . . . . . . . . . . . . . . . . 24
1.17 Parcours Eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.18 Parcours Hamiltoniens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Coloration dans les graphes 27

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 Encadrement du nombre chromatique . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Algorithme de coloration de Welsh et Powell . . . . . . . . . . . . . . . . . . . . . 28
3 Problèmes de cheminement dans les Graphes 31

3.1 Graphes sans circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.1 Source et Puits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Partition en niveaux d’un graphe sans circuits . . . . . . . . . . . . . . . . . . . . 32
3.2.1 Niveau d’un sommet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.2 Partition en niveaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.3 Ordre topologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Recherche du plus court chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 Algorithme de Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.2 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.3 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Problèmes d’ordonnancement 39
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Les tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Diagramme de Gantt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.5 Représentation par un graphe potentiels-tâches . . . . . . . . . . . . . . . . . . . 41
4.6 Recherche d’un ordonnancement optimale . . . . . . . . . . . . . . . . . . . . . . 42
4.7 Marges totales et chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5 Arbres et Arborescences 45
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2 Codage de Prüfer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.2.1 Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.2.2 Déodage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.3 L’arborescence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.4 Arbre couvrant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.5 Arbre couvrant de poids minimun . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5
6 Les flots 49
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.3 Propriétés fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.3.1 Flot maximal et coupe minimale . . . . . . . . . . . . . . . . . . . . . . . 50
6.3.2 Graphe d’écart et chemin augmentant . . . . . . . . . . . . . . . . . . . . 51
6
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 de la recherche fondamentale 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éré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.
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 suffisent
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 solution. 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
7
Introduction générale
de l’existence d’un tel chemin (appelé chemin Hamiltonien) dans un graphe quelconque.
La théorie des graphes a connu un développement plus important lors de la deuxième guerre
mondiale, et la contribution de l’armée américaine est considérable.
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 importante 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 organisation, 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.
8
Chapter 1
Concepts fondamentaux des graphes
1.1 Introduction
Les graphes représentent de manière simple et naturelle des relations entre les objets. Les out-
ils mathématiques et les algorithmes mises au point en théorie des graphes permettent 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 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 la relation ou le lien
entre les différents objets.
9
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.
x2
x1
x3
x4
x5
Figure 1.1: Un graphe non orienté
Ce graphe est défini par l’ensemble des sommets X = {x1 , x2 , x3 , x4 , x5 } et l’ensemble des
arêtes E = {{x1 , x2 }, {x1 , x4 }, {x1 , x5 }, {x2 , x2 }, {x3 , x4 }, {x3 , x5 }, {x4 , x5 }}
x2 x3
x1
x4
x6 x5
Figure 1.2: Un graphe orienté
De même pour ce graphe, l’ensemble des sommets X = {x1 , x2 , x3 , x4 , x5 , x6 } et l’ensemble

d’arcs U = {(x1 , x6 ), (x2 , x5 ), (x3 , x2 ), (x3 , x4 ), (x3 , x6 ), (x4 , x2 ), (x4 , x4 ), (x6 , x5 )}
1.2 Définitions
• L’ordre d’un graphe G est le nombre de sommets dans le graphe G.
• 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 possèdent les mêmes extrémités initiales et mêmes extrémités terminales, 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.
• Pour le cas de l’arc u : x est dit prédécesseur de y. y est dit successeur de x.
10
• 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) = {y ∈ X/(x, y) ∈ U } appelé ensemble des successeurs de x.
• Γ− (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. L’ensemble des voisins de x, noté V (x), est défini comme suit:
V (x) = {y ∈ X / x 6= y et (x, y) ∈ U ou (y, x) ∈ U }
1.3 Notion de degré

Définition 1 (Degré d’un sommet)
Soit G = (X, E) un graphe non orienté (resp. G = (X, U) un graphe orienté). Le degré d’un
sommet x ∈ X, noté dG (x), est égal au nombre d’arcs ou d’arêtes incidentes au sommet x, les
boucles étant comptées deux fois.
Dans le graphe de la figure 1.1

dG (x1 ) = 4, dG (x2 ) = 3 et dG (x3 ) = 2
Définition 2 (Demi degré d’un sommet)

Soit G = (X, U ) un graphe orienté.
Le demi-degré extérieur d’un sommet x ∈ X, noté d+ G (x), est égal au nombre d’arcs dont x est
l’extrémité initiale.
Le demi-degré intérieur d’un sommet x ∈ X, noté d− G (x), est égal au nombre d’arcs dont x est
l’extrémité terminale.
Le degré d’un sommet x: dG (x) = d+ −
G (x) + dG (x)
Dans le graphe de la figure 1.2

d+ −
G (x1 ) = 1, dG (x1 ) = 0,
+
dG (x2 ) = 1, d−
G (x2 ) = 2,
d+
G (x4 ) = 2, d−
G (x4 ) = 2.
11
Notations
• Le degré minimal d’un graphe G, noté par δ(G), est le plus petit degré dans le graphe
G. δ(G) = min{dG (x)}
• Le degré maximal d’un graphe G, noté par ∆(G), est 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
dG (x) = 2|E|
x∈X
preuve: On peut prouver cette égalité par récurrence. En effet, pour un graphe G0 ayant n
sommets et aucune (zéro) arêtes
P l’égalité est vérifiée. On suppose maintenant que l’égalité est
vraie pour m arêtes, c-à-d x∈X dG (x) = 2m, il est facile de voir que d’une part l’ajout d’une
arête augmentera de un le degré de deux sommets (ou de deux le degré d’un même sommet si
l’arête est une boucle) ce qui implique que la somme (membre gauche de l’égalité) augmentera
de deux, d’autre part le nombre d’arêtes augmente de 1, le second membre augmente donc de 2.
L’égalité est donc préservée, ce qu’il fallait montrer.
Cas orienté:
Pour tout graphe orienté G = (X, U ), on a:
X X X
dG (x) = 2|U | et d+
G (x) = d−
G (x) = |U |
x∈X x∈X x∈X
Preuve: On peut adapter la démonstration précedente.

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 Propriétés des graphes

Définition 3 (Multiplicité d’un graphe)
On appelle multiplicité d’un arc u = (x, y) (resp. arête e = {x, y}), la valeur mxy correspon-
dant au nombre d’arcs qui relient x à y. La multiplicité d’un graphe G est le nombre m(G)
correspondant au maximum des mxy . Si m(G) > 1 G est appelé multigraphe.
Si G = (X, E) (resp. G = (X, U )) est un multigraphe alors E (resp. U ) est un multi-ensemble.
Un graphe orienté est dit p-graphe si m(G) = p.
12
1.4.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.
1.4.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 .
x2 x3
x1
x4
x6 x5
Figure 1.3: Un graphe complet K6
1.4.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.
x2 x3
x1
x4
x6 x5
Figure 1.4: Un graphe 4-régulier
1.4.4 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 ∈ X2 ety ∈ X1 ).
13
G est dit biparti complet ssi G est dit biparti et ∀x ∈ X1 et ∀y ∈ X2 ⇒ (x, y) ∈ U .
x1
y1
x2
y2
x3
y3
x4
Figure 1.5: 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 .
D’autres propriétés peuvent caractériser les graphe orientés:

G est symétrique ssi ∀x, y ∈ X, (x, y) ∈ U ⇒ (y, x) ∈ U
G est antisymétrique ssi ∀x, y ∈ X, (x, y) ∈ U ⇒ (y, x) ∈ /U
G est transitif ssi ∀x, y, z ∈ X, (x, y) ∈ U et (y, z) ∈ U ⇒ (x, z) ∈ U
Remarque 1 Il existe encore d’autres types de graphes tels que:

- Les arbres et arborescences, qu’on verra en détail plus loin. - Les graphes planaires,
1.5 Sous-graphes et graphe partiel

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 Graphe partiel

Un graphe partiel G′ de G engendré par l’ensemble d’arcs (resp. d’arêtes ) V ′ ⊂ V (resp. E ′ ⊂ E)
est le graphe G′ = (X, V ) ()resp. G′ = (X, E ′ ).
1.5.2 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é.
1.5.3 Complément d’un graphe

Le graphe complémentaire de G est noté Ḡ = (X, Ē) où :
Ē = {{x, y} ∈ X 2 / x 6= y et {x, y} ∈
/ E}
14
1.6 Cliques et stables

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.1, l’ensemble de sommet S = {x2 , x3 , x4 } forme un 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.
Les ensemble de sommets {x1 , x3 , x5 } et {x1 , x4 , x5 } forment des cliques.
1.7 Représentation d’un graphe

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

1 si {xi , xj } ∈ E
Mij = (1.1)
0 sinon
 
0 1 0 1 1
1 1 0 0 0
 
 
M =
0 0 0 1 1

1 0 1 0 1
 
1 0 1 1 0
Figure 1.6: Matrice d’adjacence du graphe non orienté de la figure 1.1
Remarque 2
• 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.
Remarque 3
La somme d’une ligne i = d+ −

G (i). La somme d’une colonne j = dG (j).
15
 
0 0 0 0 0 1
0 0 0 0 1 1
 
 
0 1 0 1 0 1
M =
0

 1 0 1 0 0

0 0 0 0 0 0
 
0 0 0 0 1 0
Figure 1.7: Matrice d’adjacence du graphe orienté de la figure 1.2
1.7.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 est détectée
mais son emplacement ne peut pas être précisé à partir de cette matrice.
1.7.3 Listes
A tout graphe orienté G=(X, U) avec |X| = n et |U | = m, on peut associer deux tableaux
(vecteurs) P S et LS:
P S : tableau de pointeurs à n+1 éléments, où: P S[i] : pointe sur l’éléments (la case) de LS
contenant le premier successeur du sommet i.
On pose P S[1] = 1, On pose P S[n + 1] = m + 1.
Pour tout n > i > 2 : P S[i] = k, où k = P S[i − 1]+ nombre de successeurs de i-1
Si un sommet i n’a pas de successeurs, on aura P S[i] = P S[i + 1]
LS : tableau de m éléments, où :
Les successeurs d’un sommet i se trouvent dans LS entre la case indiquée dans P S[i] et la case
P S[i + 1] − 1.
1 2 3 4 5 6 7
PS
1 2 4 7 9 9 10
1 2 3 4 5 6 7 8 9
LS
6 5 6 2 4 6 2 4 5
Figure 1.8: Représentation par les listes de successeurs du graphe de la fig. 1.2
Il existe encore d’autres représentations, les performances des algorithmes manipulant les
16
graphes peuvent en dépendre. une représentation peut donc être plus ou moins adaptée.
1.8 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 | = |U 2| (resp. |E1 | = |E2 |) et ∀x ∈ X1 de
degré dG1 (x), ∃y ∈ X2 de degré dG2 (y) = dG1 (x).
Remarque 4 La réciproque n’est pas toujours vraie. On peut trouver deux graphes non isomor-
phes ayant le même nombre de sommets et le même nombre d’arc (ou arêtes).
1.9 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.
Pendant l’exploration du graphe un sommet peut être dans l’un des états:
- Non visité, ce sommet n’a pas encore été rencontré.
- Visité, sommet rencontré mais ces succésseurs n’ont pas été traités.
- Exploré, sommet visité et ses successeurs ont été traités.
On peut numéroter les sommet, pour chaque sommet x, ρ(x) correspond à l’ordre dans lequel
on a rencontré x. Pour chaque sommet x on peut aussi garder le sommet père pere(x) par lequel
on est passer pour rencontrer x.
17
Algorithme Exploration
Entrées
Graphe G = (X, E), (ou G = (X, U ) si le graphe est orienté) ;
Sommet de départ s ;
Début
N on-visites = X \ {s} ;
V isites = {s} ;
Explores = ∅ ;
i = 1;
Tant que V isites 6= ∅ faire
Choisir un sommet x ∈ V isites ;
Pour Chaque sommet y adjacent à x faire
Si y ∈ N on − visites Alors
N on − visite = N on − visite \ {y} ;
V isite = V isite ∪ {y} ;
Explore = Explore ∪ {x} ;
pere(y) = x ;
ρ(x) = i;
Fin si
Fait
Fait
Fin
Il existe deux grandes stratégies "opposées" pour sélectionner à chaque étape le sommet à mar-
quer:
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 exploration, l’ensemble V isits
est une pile et la procédure choisir consiste donc à dépiler un sommet (LIFO).
2. La recherche en largeur BFS (Breadth 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.10 Chaînes / Chemins
1.10.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) :
µ = x0 e1 x1 . . . xk−1 ek xk (resp. µ = x0 u1 x1 . . . xk−1 uk xk ) 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.
C1 = x1 e2 x4 e5 x3 e6 x5 est une chaine de longueur 3
18
e1 x2
x1 e7
e4
e2 x3
e5
e6
x4
e3 x5
Figure 1.10: Un graphe non orienté
u6 x3
x2
u7
u8
x1 u2 u9
u4 u5 x4
u1
u3
x6 x5
Figure 1.11: Un graphe orienté
1.10.2 Chemin
On appelle chemin dans un graphe orienté G = (X, U ), une suite alternée de sommets et d’arcs :
γ = x0 u1 x1 . . . xk−1 uk xk 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.
On dit que γ est un chemin de x0 vers xk de longueur k.
C2 = x3 u6 x2 u5 x5 u3 x6 est une chemin de longueur 3

C3 = x3 u7 x4 u9 x4 u8 x2 u2 x6 est une chemin de longueur 4
C4 = x1 u1 x6 u2 x2 u6 x3 u7 x4 est une chaine de longueur 4
1.10.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.
1.10.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 5
- 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
1.11 Cycles / Circuits

1.11.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).
1.11.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 : µ = x0 e1 x1 . . . xk−1 ek xk (resp. µ = x0 u1 x1 . . . xk−1 uk xk ) 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.
1.11.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 .
 1 si ui f ait partie du cycle dans le sens du parcours
µi = −1 si ui f ait partie du cycle dans le sens contraire du parcours
0 si ui ∈/µ

1.11.4 Circuit
On appelle circuit dans un graphe orienté G=(X, U), tout chemin fermé simple : γ = x0 u1 x1 . . . xk−1 uk xk
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 com-
posent sont distincts.
Remarques La longueur d’un cycle ou d’un circuit est aussi égale au nombre de sommets
formant ce cycle ou circuit.
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.
1.12 Connexité
Un graphe est dit connexe s’il existe une chaîne joignant chaque paire de sommets x et y (x 6= y).
20
1.13 Composante connexe (cc)

Soit un graphe G = (X, E):
La relation
soit x = y
xRy ⇔ (1.2)
soit ∃ une chaine reliant x et y
est une relation d’équivalence, les classes d’équivalence X1 , X2 , . . . Xk induites par R sur l’ensemble
de sommets X engendre les composantes connexes de G.
G comporte alors k composantes connexes.
Un graphe qui contient une seule composante connexe est dit graphe connexe.
Proposition 3 Soit G Un graphe, l’ajout d’une arête a pour conséquence :
• soit diminuer 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.
1.13.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.
1.14 Forte Connexité

Définition 7 Un graphe orienté G=(X, U) est fortement connexe 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).
1.14.1 Composantes fortement connexes (cf c)

Soit un graphe G = (X, U ):
La relation

soit x = y
xRy ⇔ (1.3)
soit ∃ un chemin de x vers y et un chemin de y vers x
est une relation d’équivalence, les classes d’équivalence X1 , X2 , . . . Xk induites par R sur l’ensemble
de sommets X engendre les composantes fortement connexes de G.
G comporte alors k composantes fortement connexes.
Un graphe qui contient une seule composante fortement connexe est dit graphe fortement
connexe.
21
1.15 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:
– 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 M arque[i] ← f aux ;
(* Recherche des descendants de r *)
Tant que (∃i ∈ D)
M arque[i] ← vrai ;
Pour tout (i, j) ∈ U D ← D ∪ {j} ;
(* Réinitialisation *)
A ← {r} ;
Pour tout i ∈ X M arque[i]f aux ;
(* Recherche des ascendants de r *)
Tant que (∃i ∈ A) et (M arque[i] = f aux)
M arque[i] ← vrai
22
Pour tout (j, i) ∈ U A ← A ∪ {j} ;

(* Calcul de la C.F.C. *)
CF C ← D ∩ A ;
1.15.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 Le graphe réduit d’un graphe ne possède pas de circuits.
1.16 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= ∅)
23
1.16.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

 1 si ui ∈ ω + (S)
θi = −1 si ui ∈ ω − (S)
0 si ui ∈/ ω(S)

1.17 Parcours Eulériens

Définition 12
Un parcours Eulérien passe une et une seule fois par chaque arête (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
(m arcs) :
Une chaîne simple, un chemin simple, un cycle simple ou un circuit simple de longueur m est
appelé Eulérien.
Définition 13
Un graphe est dit eulérien s’il admet un cycle (circuit) eulérien.
Théorème 1 Euler 1766
Un graphe non orienté 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 non orienté G admet une chaîne Eulérienne d’un sommet x à un
sommet 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) = dG (x). (On dit que G est pseudo-symétrique)
1.18 Parcours Hamiltoniens

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) Hamiltonien.
Définition 14
24
Un graphe est dit Hamiltonien ssi il admet un cycle (circuit) Hamiltonien.
Il existe une condition nécessaire et suffisante pour déterminer si un graphe est eulérien. En
revanche, pour prouver qu’un graphe est hamiltonien, on ne dispose d’aucune condition néces-
saire et suffisante. Du point de vue algorithmique aussi on dispose d’un algorithme efficace pour
vérifier qu’un graphe est eulérien mais il n’y a pas d’algorithme efficace pour vérifier qu’un graphe
est hamiltonien.
Le théorème ci-dessous est utilisé pour démontrer qu’un graphe n’est pas Hamiltonien (ne
contient pas de cycle Hamiltonien), Condition nécessaire.
Théorème 2
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.
Le théorème suivant donne une condition suffisante.
Théorème 3 (Dirac, 1952)
Un graphe simple à n ≥ 3 sommets, tel que le degré minimum est d’au moins n/2 est hamiltonien.
un autre théorème qui est dû à John Adrian Bondy et Václav Chvátal (1976) basé sur la
construction de la fermeture transitive du graphe
Définition 15
Tant qu’il reste des sommets u et v non adjacents tels que deg(u) + deg(v) ≤ n, on ajoute l’arête
{u, v} au graphe. Quand on ne peut plus en ajouter, on a obtenu ce qu’on appelle la fermeture
du graphe.
On applique alors le théorème suivant :
Théorème 4
Un graphe est hamiltonien si et seulement si sa fermeture est hamiltonienne.
x2 x2
x1 x3 x1 x3
x5 x4 x5 x4
Figure 1.12: Un graphe et sa fermeture transitive
25
Sa fermeture transitive est un graphe complet (K5 ), qui est hamiltonien, le graphe de départ
est donc hamitonien.
Malgré tous les résultats concernant l’existence de parcours hamiltoniens, dans de nombreux
cas, on ne dispose pas d’outils mathématiques efficace permettant de voir si un graphe donné
est hamiltonien ou ne pas. Ainsi, aucun des théorèmes précédents ne fournit de critère qui
permettrait de déterminer automatiquement que le graphe de la figure suivante est hamiltonien
Figure 1.13: Graphe de Wagner
26
Chapter 2
Coloration dans les graphes
2.1 Introduction
La question de coloration, datant du 19ème siècle, revêt une importance particulière en théorie
des graphes, tant sur le plan théorique que sur le plan pratique. En effet, la question célèbre du
nombre minimum de couleurs nécessaires pour colorier un graphe planaire (carte géographique)
suscite toujours autant d’intérêt. Sur le plan pratique, la coloration dans les graphes permet de
résoudre des problèmes de planification et d’emplois du temps pour ne citer que cela.
Définition 1 (Coloration d’un graphe)

La coloration des sommets d’un graphe consiste à affecter à chaque sommet de ce graphe une
couleur de telle sorte que deux sommets adjacents ne portent pas la même couleur.
Une coloration avec k couleurs est donc une partition de l’ensemble des sommets en k parties
stables.
Définition 2 (Nombre chromatique d’un graphe)

Le nombre chromatique, noté γ(G); du graphe G est le plus petit entier k pour lequel il existe
une partition de X en k sous-ensembles stables.
Exemple 1
x2
x1
x3
x4
x5
Figure 2.1: Les sommets de ce graphe peuvent être colorié avec 2 couleurs.
Définition 3 (Nombre de stabilité) On appelle nombre de stabilité, noté α(G) le cardinal

maximum d’un sous ensemble de sommets stable.
27
2.2 Encadrement du nombre chromatique

Majoration
|X|
Théorème 1 γ(G) > α(G)
Preuve: Considérons {S1; S2; . . . ; Sk} une partition de X en k parties stables avec k = γ(G)
P
( G ) étant des entiers naturels, l’inégalité de gauche est établie.
Théorème 2 Le nombre chromatique d’un graphe est supérieur ou égal à celui de chacun de ses
sous-graphes.
Preuve:
Minoration
Théorème 3 Le nombre chromatique d’un graphe est supérieur ou égal au cardinal de la clique
d’ordre maximal.
Preuve: Puisque par définition les sommets d’une clique sont tous adjacents, il faudra donc
autant de couleurs que de sommets de cette clique. Le nombre chromatique du graphe sera donc
supérieur ou égal à l’ordre de cette clique.
Théorème 4 γ(G) ≤ ∆(G) + 1
Preuve: Construisons une partition de X en sous-ensembles stables de la manière suivante:

- on considère un sommet x1 arbitraire de X; et S1 est une plus grande partie stable de X
contenant x1 .
- s’il existe un sommet x2 de X qui n’est pas dans S1 , on construit S2 ; une plus grande partie
stable de X contenant x2 disjointe de S1 - s’il existe un sommet x3 de X qui n’est pas dans S1 ∪S2
; on construit S3 ; plus grande partie stable de X contenant x3 telle que S1 ; S2 et S3 soient
deux à deux disjointes. - X étant un ensemble fini, ce procédé se terminera et nous obtenons
une partition {S1 ; S2 ; . . . ; Sk } de X: En choisissant une couleur par élément de la partition, nous
aurons nécessairement : γ(G) ≤ k.
Considérons maintenant un sommet x de la partie Sk , x est adjacent à au moins un sommet de
chaque partie Si ; i ∈ {1; 2; . . . ; k − 1}, On en déduit alors que d(x) ≥ k − 1 ≥ γ(G) − 1, ce qui
établit donc l’inégalité: γ(G) ≤ ∆(G) + 1
2.3 Algorithme de coloration de Welsh et Powell

Cet algorithme permet d’obtenir une coloration n’utilisant pas un trop grand nombre de couleurs.
Cependant il n’assure pas que le nombre de couleurs utilisé soit minimum (et donc égal au nom-
bre chromatique du graphe).
L’algorithme se déroule comme suit:
28
Etape 1 Attribuer une couleur non encore utilisée au sommet non encore coloré de degré maxi-
mum, et attribuer cette même couleur à chaque sommet non encore coloré et non adjacent
à un sommet de cette couleur.
Etape 2 S’il reste des sommets non colorés dans le graphe, revenir à l’étape 1. Sinon, la col-
oration est terminée.
29
30
Chapter 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 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.
Tout graphe sans circuits possède une source et un puits.
Le graphe précédent est un graphe sans circuits, les sommets x1 et x6 sont des sommets sources
et le sommet x8 est un sommet puits.
Proposition 9 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 10 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.
31
Problèmes de cheminement dans les Graphes
x2 x4 x6
x1 x8
x3 x5 x7
Figure 3.1: Graphe sans circuits
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 un entiers v(x) corre-
spondant au niveau du sommet x et représentant la longueur du chemin de longueur maximale
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) = max{v(x)}.
x∈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, chaque sommet de niveau i sera placé dans le stable Ni . Chaque
stable Ni représente un niveau de G.
Ainsi les niveaux du graphe précédent sont:

N0 = {x1 , x6 }
N1 = {x2 }
N2 = {x3 }
N3 = {x4 , x5 }
N4 = {x7 }
N5 = {x8 }
Proposition 11 G=(X,U) est un graphe sans circuits si et seulement si X admet une parti-
tion {N0 ∪ N1 ∪ . . . ∪ Np } tel que x ∈ Ni ⇔ v(x) = i
3.2.3 Ordre topologique

Un ordre topologique (ou tri topologique) d’un graphe orienté sans circuits est une numérotation
des sommets associant à chaque sommet x un numéro n(x) tel que pour chaque arc u = (xy),
n(x) < n(y).
L’une des méthodes permettant d’obtenir l’ordre topologique d’un graphe, est de numéroter
les sommets par niveau, en commençant par les sommets de N0 , puis ceux de N1 , etc ...
32
L’ordre topologique est utilisé dans l’algorithme de Bellman pour déterminer le plus court
chemin dans un graphe.
L’ordre topologique (en rouge) du graphe de la figure 3.1 est:
x2 (2) x4 (4) x6 (1)
x1 x8
(0) (7)
x3 (3) x5 (5) x7 (6)
Figure 3.2: Graphe sans circuits
3.3 Recherche du plus court chemin

Etant donné un sommet x, déterminer pour chaque sommet y le plus court chemin (ou chemin
de poids minimum) de x à y.
Plusieurs algorithmes ont été développé pour la recherche du plus court chemin dans un graphe,
mais avant de présenter quelques algorithmes nous donnons d’abord ces définitions.
Définition 4 (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.
Ces poids peuvent correspondre à des coûts, des distances, des temps, . . .
Définition 5 (Poids d’un chemin)

X
On définit le poids d’un chemin γ comme la somme des poids des arcs de γ, p(γ) = p(u).
u∈γ
3.3.1 Algorithme de Bellman

L’algorithme de Bellman, qui ne s’applique que pour des graphes sans circuits, est basé sur
l’équation dite équation de Bellman, utilisée en programmation dynamique. Cette équation est
énoncée comme suit:
π(y) = min (π(y), π(x) + p(xy))
∀x∈Γ− (y)
Soit un graphe G = (X, U, p) un graphe orienté pondéré sans circuits, et soit s ∈ X, un som-
met de départ, l’algorithme détermine le chemin de poids minimum vers tous les autres sommets
atteignables à partir du sommet s.
33
L’algorithme se base sur un graphe dont les sommets sont numérotés selon l’ordre topologique
tel que n(s) = 0.
Algorithme de Bellman:
π(x0 ) = 0;
π(xi ) = +∞, ∀1 ≤ i ≤ n ;
pour j = 1 à n faire
pour tout xi ∈ Γ− (xj ) faire
si π(xj ) > π(xi ) + p(xi xj ) alors
π(xj ) = π(xi ) + p(xi xj ) ;
opt(xj ) = xi ;
fait
fait
opt(j) correspond au sommet précédant le sommet j sur le plus court chemin allant de s à j.
La boucle interne est équivalente à π(y) = min (π(y), π(x) + p(xy)).
∀x∈Γ− (y)
La complexité de cet algorithme est O(m) correspondant à une complexité en O(n2 ).
Exemple 2
On considère le graphe orienté sans circuits suivant, on veut déterminer les plus court chemins
partant du sommet x0 vers tous autres sommets:
x3 4 x4 4 x1
5 5
6
x0 3 3 2 x7
7
1 5 8 3
x2 x5 x6
Figure 3.3: Graphe pondéré
Initialisation π(x0 ) = 0;
π(xi ) = +∞, ∀1 ≤ i < n ;
Iteration pour j = 1
Γ− (x1 ) = ∅ ;
π(x1 ) = min(+∞) = +∞; Il n’y a pas de chemin de x0 vers x1 .
Γ− (x2 ) = {x0 } ;
π(x2 ) = min(π(x2 ), π(x0 ) + p(x0 x2 )) = min(∞, 0 + 1) = 1 ;
opt(x2 ) = x0 ;
Γ− (x3 ) = {x0 , x2 } ;
34
π(x3 ) = min(π(x3 ), π(x0 ) + p(x0 x3 ), π(x2 ) + p(x2 x3 )) = min(+∞, 0 + 5, 1 + 3) = 4;

opt(x3 ) = x2 ;
Γ− (x4 ) = {x2 , x3 } ;
opt(x4 ) = x2 ;
Γ− (x5 ) = {x2 , x3 } ;
opt(x5 ) = x2 ;
Γ− (x6 ) = {x1 , x4 , x5 } ;
π(x6 ) = min(π(x6 ), π(x1 ) + p(x1 x6 ), π(x4 ) + p(x4 x6 ), π(x5 ) + p(x5 x6 ))
= min(+∞, +∞ + 2, 7 + 3, 6 + 8) = 10 ;
opt(x6 ) = x4 ;
Γ− (x7 ) = {x6 } ;
π(x7 ) = min(π(x7 ), π(x6 ) + p(x6 , x7 )) = min(+∞, 10 + 3) = 13 ;
opt(x7 ) = x6 ;
[4, x2 ] [7, x2 ] [+∞, −]

x3 4 x4 4 x1
5 5
[0, −] 6 [13, x6 ]
x0 3 3 2 x7
7
1 5 8 3
x2 [1, x0 ] x5 [6, x2 ] x6 [10, x4 ]
Figure 3.4: Graphe pondéré
Le plus court chemin allant de x0 à x7 est en vert, qu’on peut déduire grâce à opt. En effet:
opt(x7 ) = x6 , opt(x6 ) = x4 , opt(x4 ) = x2 , opt(x2 ) = x0 . Le poids du chemin x0 x2 x4 x6 x7 est
π(x7 ) = 13
De même on peut déterminer le plus court chemin allant de x0 à x3 :
opt(x3 ) = x2 , opt(x2 ) = x0 , c’est donc x0 x2 x3 , son poids est π(x3 ) = 4.
3.3.2 Algorithme de Dijkstra

L’algorithme de Dijsktra permet de trouver le plus court chemin partant d’un sommet s vers
tout les sommets dans un graphe pouvant contenir des circuits non absorbants.
Définition 6 (Circuit absorbant)
Un circuit γ est dit absorbant si son poids est négatif (p(γ) < 0).
35
Principe: L’algorithme calcule le chemin de poids minimal en partant du sommet s et en pro-

longeant le chemin à chaque itération. A chaque étape, pour un sommet donné x, on ajuste les
valeurs de π(y) pour tout sommet y ∈ Γ+ (x) successeur de x.
On utilisera un ensemble T ⊂ X qui contiendra les sommets non encore traités.
Algorithme de Dijsktra π(x0 ) = 0;

π(xi ) = +∞, ∀1 ≤ i ≤ n ;
S=X ;
tant que S 6= ∅ faire
choisir un sommet x ∈ S tel que π(x) = min (π(y)) ;
∀y∈S
retirer x de S ;
pour tout y ∈ Γ+ (x) faire
si π(y) > π(x) + p(xy) alors
π(y) = π(x) + p(xy) ;
opt(y) = x ;
fsi
fait
fait
fin.
On reprend le graphe de la figure 3.1 pour déterminer les plus court chemin à l’aide de
l’algorithme de Dijkstra. Nous allons utiliser un tableau où chaque ligne correspond à une itéra-
tion où le minimum choisit est l’élément souligné à la ligne précédente.
x0 x1 x2 x3 x4 x5 x6 x7
0 +∞ +∞ +∞ +∞ +∞ +∞ +∞
x0 · +∞ 1 5 +∞ +∞ +∞ +∞
x2 · +∞ · 4 7 6 +∞ +∞
x3 · +∞ · · 7 6 +∞ +∞
x5 · +∞ · · 7 · 14 +∞
x4 · +∞ · · · · 10 +∞
x6 · +∞ · · · · · 13
x7 · +∞ · · · · · ·
x1 · · · · · · · ·
La complexité de cet algorithme est O(m) qui correspond donc à une complexité en O(n2 ).
3.3.3 Algorithme de Bellman-Ford

L’algorithme de Bellman-Ford permet de trouver les plus courts chemins partant d’un sommet
s = x0 dans un graphe même si celui-ci comporte des circuits et détecte la présence de circuits
absorbants.
A chaque sommet x ∈ X, on veut associer un chemin de poids optimal joignant la source du
graphe s ∈ X à x dans le réseau R = (X, U, p)
Principe: L’algorithme consiste à calculer dkx correspondant au plus court chemin entre s et x
comportant au plus k arcs.
• d0x = +∞, ∀x 6= s, d0s = 0.
36
• dkx = min{dxk−1 , min (dyk−1 + p(yx)}

∀y∈Γ+ (x)
Algorithme de Bellman-Ford:
d0s = 0 ; d0x = +∞, ∀x 6= s,
pour k = 1 à n − 1 faire
pour chaque arc (x, y) faire
si dy > dx + p(xy) alors
dy = dx + p(xy) ;
opt(y) = x ;
fsi
fait
fait
pour chaque arc (x, y) faire
si dy > dx + p(xy) alors
afficher("Existence d’un circuit absorbant") ;
fsi
fait
fin.
La complexité de cet algorithme est O(n × m) qui correspond à une complexité en O(n3 ).
Remarque 7
On peut effectuer la recherche du plus long chemin dans un graphe de deux manières: Soit en
adaptant les algorithmes de recherche du plus court chemin (initialisation, comparaison, ...), soit
en replaçant le poids de chaque arc par sa négation.
Dans le cas de la recherche du plus long chemin, un circuit est dit absorbant si son poids est
positif.
37
38
Chapter 4
Problèmes d’ordonnancement
4.1 Introduction
On a affaire à un problème d’ordonnancement lorsque l’on est confronté à un problè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écessaire 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éalisation 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.
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).
39
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 , et on a la relation fi = 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 i ne peut débuter que si une certaine autres tâche j est finie. Une telle contrainte
peut être représentée par la relation:
ti ≥ tj + dj ou encore ti − tj ≥ dj
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.
Exemple 3
Considérons le problème d’ordonnancement ayant les tâches a, b, c, d, e et f , et dont les con-

traintes de précédence sont données dans le tableau 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
40
Le diagramme de Gantt associé:
Tâches
f
e
d
c
b
a
t
1 2 3 4 5 6 7 8 9
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 représente une tâche.
• Les arcs U représente les contraintes de potentiels (de précédence en général):
U = {u = (i, j)/ ∃ une contrainte tj − ti 6 aij }
Le poids associé à un arc (i, j) est pij = aij .
• On ajoute à cela deux sommets α et ω représentant 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.
6
a f
2
0 3
3 d
0
α b 4 ω
3 e
0
6
c
Figure 4.2: Le graphe Potentiels-Tâches
41
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 5 Il existe un ordonnancement réalisable si et seulement si il n’existe pas de circuit

de valeur strictement positive dans G.
Si la condition d’existence est vérifiée alors, il existe un ordonnancement réalisables de durée

minimale.
La détermination du calendrier optimal consiste à déterminer (tα , t1 , t2 , . . . , tn , tω ) de façon

à:
Minimiser (tω − tα ) sous les conditions :
1. Contraintes de potentiel : tj − ti > aij
2. Contraintes de non négativité : tα , t1 , . . . , tn , tω > 0
Théorème 6 Dans le cas d’un graphe sans circuit, on a
t0 = 0, ti = max (tj + vji )

j∈Γ
−1 (i)
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ω
Théorème 7 Dans le cas d’un graphe sans circuits, on a
tω = tω , ti = min (tj + vij )

j∈Γ(i)
42
4.7 Marges totales et chemin critique

Définition 7 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.
M i = ti − ti
Définition 8 Les tâches critiques ont une marge nulle, tout retard sur leur exécution entraîne
un retard global dans le projet.
Un chemin est critique s’il relie α et ω et s’il ne contient que des tâches critiques.
Définition 9 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 = min (tk − ti − di )
k∈Γ(j)
43
44
Chapter 5
Arbres et Arborescences
5.1 Introduction
Les arbres sont des graphes particuliers, très utilisés en algorithmiques et en informatique.
Définition 10 Un arbre est un graphe connexe sans cycle. Une forêt est un graphe sans cycle.
x2
x1
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.
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 8 Pour un graphe T d’ordre n, il y a équivalence entre les propriétés :
45
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 Codage de Prüfer

Soit l’arbre T = (X, E) et supposons X = {x1 , x2 , ..., xn }.
5.2.1 Codage
L’algorithme ci-dessous fournira le code de T , c’est-à-dire une suite S de n − 2 termes employant
(éventuellement plusieurs fois) des nombres choisis parmi {1, ..., n}.
Pas général de l’algorithme de codage (à répéter tant qu’il reste plus de deux sommets dans
l’arbre courant T )
• identifier la feuille x de l’arbre courant ayant le numéro minimum ;
• ajouter à la suite S le seul sommet s adjacent à x dans l’arbre T courant ;

• enlever de l’arbre T courant le sommet x et l’arête incidente à x.
5.2.2 Déodage
Etant donnée une suite S de n−2 nombres, chacun provenant de {1, ..., n}. Posons I = {1, ..., n}.
Pas général de l’algorithme de décodage (à répéter tant qu’il reste des éléments dans S et plus
de deux éléments dans I)
• identifier le plus petit élément i de I n’apparaissant pas dans la suite S ;
46
• relier par une arête de T le sommet i avec le sommet s correspondant au premier élément
de la suite S ;
• enlever i de I et s de S.
Les deux éléments qui restent dans I à la fin de l’algorithme constituent les extrémités de la
dernière arête à ajouter à T .
Théorème 9 (Cayley, 1857) Le nombre d’arbres que l’on peut construire sur n (n > 1) sommets
numérotés est égal à nn−2 .
5.3 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.
5.4 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. Connecter 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 11 Un arbre couvrant pour un graphe G = (V, E) est un arbre construit unique-
ment à 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.
47
5.5 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 mini-
mum (MST, Minimum Spanning Tree):
• 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)).
48
Chapter 6
Les flots
6.1 Introduction
Les flots permettent de modéliser une très large classe de problèmes. Leur interprétation corre-
spond à 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 12 (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.
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 13 (Le flot)

Un flot ϕ sur un réseau R = (X, U ) est une valuation positive ϕ des arcs, ϕ est une application
49
Les flots
6
a f
2
7 4
3 d
4 4
s b 5 t
3 e
5
3 4
c
Figure 6.1: Un réseau
définie de U dans ℜ+ , telle que: pour tout sommet x ∈ U \ {s, t},

P P
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).
P P
P comme le flux net sortant de s ( x ϕ(s, x) − x ϕ(x, s)) ou
La valeur duPflot est définie
entrant dans t ( x ϕ(x, t) − x ϕ(t, x)) .
Définition 14 (Flot maximum)

Un flot maximum dans un réseau est un flot compatible de valeur maximale.
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.
X
v(S, T ) = c(u)
u∈ω + (S)
Théorème 10 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.
50
Les flots
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 µ 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.
4
a f
1
4 4
1 d
4 1
s b 5 t
3 e
5
1 4
c
Figure 6.2: Un flot
51
Les flots
52

TH Graphes

Transféré par

Droits d'auteur :

Formats disponibles

TH Graphes

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

TH Graphes

Transféré par

Droits d'auteur :

Formats disponibles

Ministère de l’Enseignement Supéieur et de la Recherche Scientifique

Université des Sciences et de la Technologie Houari Boumediene

Théorie des Graphes

1 Concepts fondamentaux des graphes 9

2 Coloration dans les graphes 27

3 Problèmes de cheminement dans les Graphes 31

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

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

Concepts fondamentaux des graphes

1.1.1 Graphe orienté

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

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

1.1.2 Graphe non orienté

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

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

1.1.3 Représentation graphique

Figure 1.1: Un graphe non orienté

Figure 1.2: Un graphe orienté

De même pour ce graphe, l’ensemble des sommets X = {x1 , x2 , x3 , x4 , x5 , x6 } et l’ensemble

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

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

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

• Γ− (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

V (x) = {y ∈ X / x 6= y et (x, y) ∈ U ou (y, x) ∈ U }

1.3 Notion de degré

Dans le graphe de la figure 1.1

Définition 2 (Demi degré d’un sommet)

Dans le graphe de la figure 1.2

1.3.1 Formule des degrés

Preuve: On peut adapter la démonstration précedente.

1.4 Propriétés des graphes

Si G = (X, E) (resp. G = (X, U )) est un multigraphe alors E (resp. U ) est un multi-ensemble.

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

1.4.1 Graphe Simple

1.4.2 Graphe Complet

Figure 1.3: Un graphe complet K6

1.4.3 Graphe Régulier

Figure 1.4: Un graphe 4-régulier

1.4.4 Graphe Biparti

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

Figure 1.5: Un graphe biparti

D’autres propriétés peuvent caractériser les graphe orientés:

Remarque 1 Il existe encore d’autres types de graphes tels que:

1.5 Sous-graphes et graphe partiel

1.5.1 Graphe partiel

1.5.2 Sous graphe

1.5.3 Complément d’un graphe

1.6 Cliques et stables

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

1.7 Représentation d’un graphe

Figure 1.6: Matrice d’adjacence du graphe non orienté de la figure 1.1

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

La somme d’une ligne i = d+ −

Figure 1.7: Matrice d’adjacence du graphe orienté de la figure 1.2

1.7.2 Matrice d’incidence

Figure 1.9: Deux graphes isomorphes