LINMA1691 - Théorie et Algorithmique des

Graphes
Robin Ballarini Annelies Bauwens Gilles Bertrand
Armand Bosquillon de Jenlis Alexandre Bovet
Romain Capron Arnaud Cerckel Charlotte Cirriez
Simon Claessens Thibault Clavier Gaëtan Collart
Matthieu Constant Xavier Crochet Benoit Daloze
Gatien De Callataÿ François Dederichs Sébastien De Fauw
François Delcourt Arnaud de Lhoneux Martin De Neuville
Guillaume Derval Alexandre de Touzalin Gauthier Feuillen
Florentin Goyens Arnaud Jacques Antoine Hilhorst
Benoît Legat Thibault Liénart Arthur Losseau
Alexis Pierret Thérèse Plissart François Raucent
Félicien Schiltz Mélanie Sedda Benoît Sluysmans
Nicolas Stevens Harold Taeter Kim Van Den Eeckhaut
Geoffroy Vanderreydt Antoine Van Malleghem Nicolas Vico
Romain Hollanders Florimond Houssiau
Vincent Schellekens Jean-Charles Delvenne

5 janvier 2022
Notes partielles et provisoires
Table des matières
1 Graphes connexes, eulériens et bipartis 3
1.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Isomorphisme de Graphes . . . . . . . . . . . . . . . . . . . . 4
1.3 Parcours eulérien . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Représentation matricielle du graphe . . . . . . . . . . . . . . 8
1.5 Graphes bipartis . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Les plus courts chemins 14

2.1 Les plus courts chemins . . . . . . . . . . . . . . . . . . . . . 14
2.2 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Anneaux et Semi-anneaux . . . . . . . . . . . . . . . . . . . . 19

3 Arbres et connectivité 21
3.1 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Arbre sous-tendant de poids minimum . . . . . . . . . . . . . 24
3.3 Connectivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Graphes hamiltoniens 34

5 Mariages, couplages et couvertures 37

5.1 Couplage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Couverture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3 L’algorithme hongrois . . . . . . . . . . . . . . . . . . . . . . 43

6 Coloriages d’arêtes 45

7 Cliques, ensembles indépendants et l’impossible désordre 48

7.1 Ensembles indépendants . . . . . . . . . . . . . . . . . . . . . 48
7.2 Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7.3 La théorie de Ramsey . . . . . . . . . . . . . . . . . . . . . . 53

8 Coloriages de sommets 56
8.1 Coloriages de sommets et nombre chromatique . . . . . . . . 56
8.2 Bornes sur le nombre chromatique . . . . . . . . . . . . . . . 56
8.3 Polynôme chromatique . . . . . . . . . . . . . . . . . . . . . . 59

9 Graphes planaires 61
9.1 Graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . 62
9.2 Formule d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . 66
9.3 Les cinq solides platoniciens . . . . . . . . . . . . . . . . . . . 68
9.4 Coloriage des graphes planaires . . . . . . . . . . . . . . . . . 69

1
10 Flots et coupes 71
10.1 Flots et coupes . . . . . . . . . . . . . . . . . . . . . . . . . . 71
10.2 L’algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . . 75

11 P, N P et N P-complétude 77
11.1 P, N P et N P-complétude . . . . . . . . . . . . . . . . . . . . 77

2
1 Graphes connexes, eulériens et bipartis
Dans cette section, les notions de base de la théorie des graphes sont
définies, et ses résultats élémentaires sont exposés et démontrés. Dans un
premier temps, on s’intéresse à la définition de la notion de graphe, et celle
d’isomorphisme entre graphes. Ensuite, on étudie les graphes eulériens, et on
démontre un résultat fondamental permettant de prouver facilement qu’un
graphe est ou n’est pas eulérien. Puis les représentations d’un graphe sous
forme matricielle sont définies, et leur intérêt est montré au travers du théo-
rème dit des poignées de main. Enfin, on définit ce qu’est un graphe biparti,
et fait le lien entre cette notion et la présence de cycles impairs dans un
graphe.

1.1 Graphes
Définition 1.1. Un graphe est un triplet (V , E, ϕ), où :
— V est un ensemble fini dont les éléments sont appelés sommets ou
noeuds ;
— E est un ensemble fini dont les éléments sont appelés arêtes ;
— ϕ est une fonction, dite fonction d’incidence, qui associe à chaque
arête un sommet ou une paire de sommets.

Définition 1.2. Deux sommets incidents à la même arête sont dits adja-
cents.

Définition 1.3. Une arête incidente à un seul sommet est une boucle. Deux
arêtes sont dites multiples si elles sont toutes deux incidentes aux mêmes
noeuds.

Définition 1.4. Le degré d’un sommet est le nombre d’arêtes incidentes à

celui-ci, les boucles comptant comme arêtes doublement incidentes.

Définition 1.5. Un sous-graphe du graphe (V , E, ϕ) est un graphe (V 0 , E 0 ,

ϕ0 ) avec :
— V0 ⊆V ;
— E0 ⊆ E ;
— ϕ0 est la restriction de ϕ à E 0 .
Le sous-graphe induit par un ensemble de noeuds V 0 ⊆ V est le sous-
graphe dont l’ensemble des noeuds est V 0 et l’ensemble des arêtes est E 0 =
{e ∈ E : ϕ(e) ⊆ V 0 }, autrement dit les arêtes dont les extrémités sont dans
V 0.

Définition 1.6. Un graphe est dit simple si :

3
 1. il n’a pas de boucle ;
2. il n’a pas d’arête multiple.

Exemple 1.7. Soit V = {1, 2, 3, 4}, et E = {a, b, c, d, e, f }, on définit la

fonction ϕ : E −→ V × V comme :

ϕ(a) = {1, 1}
ϕ(b) = {1, 2}
ϕ(c) = {1, 2}
ϕ(d) = {2, 3}
ϕ(e) = {1, 3}
ϕ(f ) = {3, 4}

Soit G = (V, E, ϕ) : c’est un graphe, et on peut le représenter comme

suit (figure 1(a)). Par définition, l’arête a est une boucle, les arêtes b et c
sont dites multiples, et les trois noeuds sont adjacents les uns aux autres.
Leurs degrés respectifs sont (5, 3, 3, 1).
Ce graphe n’est pas simple : il possède une boucle et des arêtes multiples.
Par contre, si on définit V 0 = {1, 2, 3} et E 0 = {b, d, e}, et soit ϕ0 la restriction
de ϕ à E 0 , on obtient le sous-graphe G0 = (V 0 , E 0 , ϕ0 ) de G, représenté à la
figure 1(b) ci-dessous. Ce sous-graphe est simple.

1 1

e b e b
c
4 3 2 3 2
f d d
(a) (b)

Notons que dans un graphe simple, puisqu’il n’y a qu’une seule arête
possible entre deux noeuds u et v, la fonction d’incidence ϕ est injective : au
plus une arête e existe telle que ϕ(e) = {u, v}. On se permet donc souvent
l’abus de notation e = {u, v}, ou plus simplement encore e = uv, puisque
cela ne génère pas d’ambiguité.

1.2 Isomorphisme de Graphes

Définition 1.8. Deux graphes (V , E, ϕ) et (V 0 , E 0 , ϕ0 ) sont dits isomorphes
s’il existe des bijections f : V → V 0 et g : E → E 0 telles que :

ϕ(e) = {u, v} ssi ϕ0 (g(e)) = {f (u), f (v)}

4
pour tous e ∈ E, u ∈ V, v ∈ V .

Cette notion permet de généraliser la notion d’égalité entre graphes,

en ce sens que deux graphes isomorphes sont essentiellement les mêmes,
et partagent leur propriétés ‘en tant que graphes’. En d’autres termes, on
pourrait dire qu’un graphe G1 isomorphe à un autre graphe G2 est le résultat
d’une simple renumérotation de G2 (et vice-versa).
L’isomorphisme entre les graphes est une relation d’équivalence entre
graphes : cela se vérifie facilement à partir de la définition.

Exemple 1.9. Voici deux exemples d’isomorphisme du même graphe : No-

1 a 10 e0
e a0
10
e0 a0
5 2 50 20 30 40
b0
d b d0 c0 d0 c0
4 3 50 20
c 40 30 b0
(c) (d) (e)

tons que, même si cela ne parait pas forcément évident, les graphes (d) et
(e) sont les mêmes (et pas seulement isomorphes) : ils ont la même fonction
d’incidence entre le même ensemble d’arêtes et le même ensemble de noeuds
mais ils sont simplement dessinés différemment sur le papier.
L’isomorphisme entre (c) et les deux autres est donné par :

f (1) = 10 g(a) = e0
f (2) = 40 g(b) = c0 ϕ(a) = {1, 2}
f (3) = 20 g(c) = b0 ϕ0 (a0 ) = {10 , 30 }
f (4) = 50 g(d) = d0 ϕ0 (g(a)) = {f (1), f (2)}
f (5) = 30 g(e) = a0
Notons aussi que plusieurs résultats sont possibles :

1 a 10 a0
e e0
10
e0 a0
5 2 50 20 40 30
d0
d b b0 c0 c0 b0
4 3 20 50
c 40 30 d0
(f) (g) (h)

5
 f (1) = 10 g(a) = a0
f (2) = 30 g(b) = b0
f (3) = 50 g(c) = d0
f (4) = 20 g(d) = c0
f (5) = 40 g(e) = e0
Les six graphes de cet exemple sont isomorphes entre eux.

Difficulté : déterminer si deux graphes sont isomorphes est un pro-

blème algorithmiquement difficile : on ne connaît pas de procédure beau-
coup plus rapide que la force brute (essayer toutes les bijections possibles
à la recherche d’un isomorphisme). En revanche, il est possible dans
de nombreux cas particuliers de démontrer que deux graphes ne sont
pas isomorphes par des arguments simples, en employant le fait que
deux graphes isomorphes partagent les mêmes propriétés, notamment
en terme de présence de cycles (cette notion est définie par la suite).
Par exemple, si un graphe possède un triangle (cycle de longueur
3), mais pas l’autre, alors on sait de façon certaine qu’il n’existe pas
d’isomorphisme entre ces graphes.

1.3 Parcours eulérien

Définition 1.10. Un parcours est une séquence de sommets et d’arêtes
v0 , e0 , v1 , e1 , ..., en−1 , vn telle que toute arête ei de ce parcours a pour extré-
mités les sommets vi et vi+1 . Les sommets v0 et vn sont les extrémités du
parcours. La longueur du parcours est n, le nombre d’arêtes parcourues. Un
parcours peut contenir plusieurs fois un même sommet ou une même arête.
Il est fermé si v0 = vn .

Définition 1.11. Un chemin est un parcours dont tous les sommets (sauf
éventuellement les extrémités, voir définition suivantes) sont distincts et
toutes les arêtes sont distinctes.

Définition 1.12. Un cycle est un chemin fermé.

Théorème 1.13. Un graphe est connexe ssi pour chaque paire de sommets,
il existe un parcours qui les relie. Les composantes connexes d’un graphe sont
ses sous-graphes connexes maximaux.
On démontre aisément la proposition suivante.
Théorème 1.14. Un graphe est connexe si et seulement si pour tout en-
semble non vide de noeuds S, de complémentaire S non vide, il y a au moins
une arête entre S et S.

6
Définition 1.15. Un parcours est eulérien s’il visite chaque arête du graphe
une et une seule fois. Un graphe est eulérien s’il existe un parcours eulérien
fermé dans ce graphe.

Théorème 1.16 (Théorème d’Euler). Un graphe connexe est eulérien ssi

tous les sommets sont de degré pair.

Démonstration.
=⇒
Chaque arête incidente à un noeud x est utilisée une et une seule fois par le
parcours eulérien :
— soit pour entrer dans x ;
— soit pour en sortir.
À chaque arête entrante correspond une arête sortante (celle qui suit dans
le parcours sauf pour la dernière arête du parcours qui correspond à la pre-
mière).
Donc, en chaque noeud il y a une bijection entre les arêtes entrantes et les
arêtes sortantes.
Donc chaque noeud a un degré pair.

⇐=
On va construire un parcours eulérien :
1. On part d’un noeud arbitraire x0 .
2. On prend une arête incidente à x0 , on arrive à un nouveau noeud.
3. Par parité, il y a au moins une arête non utilisée, on la prend, on
arrive à un autre noeud, on ressort par une arête disponible (si elle
existe), etc. Ce processus doit finir puisque le nombre d’arêtes est fini.
Quand il n’y a plus d’arête disponible, on est forcément arrivé à x0
car pour tout autre noeud y, en arrivant à y, on a utilisé un nombre
impair d’arêtes incidentes à y, donc il en reste au moins une non encore
visitée par le parcours.
On a donc un parcours fermé P0 :
— Si toutes les arêtes incidentes aux noeuds traversés par ce parcours
sont utilisées, alors ce parcours est eulérien ;
— Sinon, il y a un noeud x1 avec une arête non visitée. On prétend que
ce x1 peut être choisi sur le parcours P0 déjà construit. En effet, par
connexité, il y a au moins une arête entre un noeud déjà visité par
P0 et un noeud non visité (en vertu du Théorème 1.14). On choisit
ce noeud déjà visité comme x1 .
— A partir de x1 , on crée un parcours P1 sur le graphe des arêtes non
encore visitées par P0 : c’est un graphe dont les degrés sont pairs,
puisque chaque P0 visite un nombre pair d’arêtes à chaque noeud.

7
 x0 x1

On fusionne les deux parcours :

P0+1 = x0 →x1 →x1 →x0

(les couleurs se réfèrent au dessin) et on répète l’argument jusqu’à inclure

toutes les arêtes dans le parcours, et obtenir ainsi un parcours eulérien.

Théorème 1.17 (Existence d’un parcours eulérien). Un graphe connexe

possède un parcours eulérien ssi le nombre de noeuds de degré impair est
zéro ou deux.

Démonstration.
=⇒

— Si ce parcours eulérien est fermé, tous les degrés sont pairs par le
théorème précédent ;
— Si ce parcours eulérien est ouvert d’origine u et destination v, tous
les degrés sont pairs, sauf deg(u) et deg(v) qui sont impairs, par une
légère adaptation de l’argument du cas fermé.
⇐=

— Si tous les degrés sont pairs alors il existe un parcours eulérien fermé
par le théorème précédent ;
— Si les degrés de u et v sont impairs et si on ajoute une arête e entre
u et v :
→ Tous les degrés sont pairs.
→ Il existe un parcours eulérien fermé.
En retirant e, on obtient un parcours eulérien ouvert u → v.

1.4 Représentation matricielle du graphe

Définition 1.18. La matrice d’incidence est une matrice rectangulaire n×m
dont l’élément ij est le nombre de fois que le sommet vi est incident à l’arête
ej . Une boucle compte pour deux.

La matrice d’incidence est une représentation commode de la fonction

d’incidence qui définit un graphe.

8
Définition 1.19. La matrice d’adjacence est une matrice carrée n × n dont
l’élément ij est le nombre d’arêtes entre les sommets vi et vj . Une boucle
compte pour un dans l’élément diagonal correspondant.

Un exemple d’application de la matrice d’incidence est le théorème des

poignées de mains :

Théorème 1.20 (Théorème des poignées de mains). La somme des degrés

des noeuds d’un graphe est deux fois le nombre d’arêtes.
X
deg(vi ) = 2|E|
vi ∈V

Démonstration. En utilisant la matrice d’incidence M (voir Définition 1.18),

P
on peut calculer ij Mij de deux façon différentes : chaque ligne représente
le degré du noeud correspondant, et chaque colonne (représentant une arête)
somme
 à deux. 
0 1 1 0 1 0
 
 1 1 0 1 0 1  P P P
i j Mij = vi ∈V deg(vi )
 
 1 0 0 1 0 1 
 
0 0 1 0 1 0
P P P
j i Mij = j 2 = 2|E|
XX XX
Mij = Mij
i j j i
X
deg(vi ) = 2|E|.
vi ∈V

Une application de la matrice d’adjacence est la suivante :

Théorème 1.21 (Matrice d’adjacence et nombre de parcours). Soit A la

matrice d’adjacence d’un graphe. Alors l’élément ij de Ak (k ≥ 0) est le
nombre de parcours de longueur k de vi vers vj .

Démonstration. Nous procédons par récurrence. Soit A une matrice d’adja-

cence.
Initialisation Pour k = 0, A0 = I. La propriété est vérifiée par convention.
Il existe un chemin de longueur 0 d’un point vers lui même.
Pour k = 1, A1 = A représente bien le nombre de parcours de longueur
1.

9
Induction Supposons la propriété vérifiée pour Ak .

#parcours i → j longueur k + 1
X
= (#parcours i → l longueur k) · (#arêtes l → j)
l∈V
X
= Akil Alj
l∈V
= Ak+1
ij .

e b
c

3 2
d

Figure 1 – Graphe de l’exemple 1.22.

Exemple 1.22. La matrice d’adjacence de la figure 1 est

1 2 3
 
1 1 2 1
A = 22 0 1
 
3 1 1 0

et sa matrice d’incidence est

a b c d e
 
1 2 1 1 0 1
M = 20 1 1 1 0 .
 
3 0 0 0 1 1

(Ak )ij est le nombre de parcours i → j de longueur k.

10
  
1 0 0
0
A = I = 0 1 0 ,
 
0 0 1
 
1 2 1
A1 = A = 2 0 1 ,
 
1 1 0
 
6 3 3
2
A = 3 5 2 .
 
3 2 2

Définition 1.23. La distance d(u, v) entre les noeuds u et v d’un graphe

est le nombre d’arêtes minimal d’un parcours entre ces deux noeuds.

Lemme 1.24. Si u...u0 ...v 0 ...v est un parcours de longueur minimale de u

vers v, alors le sous-parcours u0 ...v 0 est un parcours de longueur minimale
de u0 vers v 0 .
En particulier, un parcours de longueur minimale est toujours un chemin.

Démonstration. Si ce parcours entre u0 et v 0 n’était pas le plus court, on uti-

liserait le parcours strictement plus court pour la construction du parcours
entre u et v.

1.5 Graphes bipartis

Définition 1.25. Un graphe est biparti s’il existe une partition des noeuds
en deux ensembles V0 et V1 tels que les noeuds de V0 ne sont adjacents qu’à
des noeuds de V1 et vice versa. La bipartition est (V0 , V1 ).

Exemple 1.26.

11
 V0
V1
1
6
2
7
3
8
4
9
5

Théorème 1.27 (Cycles et parcours dans les graphes bipartis). Un graphe

est biparti ssi tous ses parcours fermés sont de longueur paire ssi tous ses
cycles sont de longueur paire.

Démonstration.
biparti =⇒ parcours fermés de longueur paire
On suppose qu’il existe une bipartition (V0 , V1 ). Soit un parcours fermé
v0 e0 v1 e1 v2 . . . vn−1 en−1 v0 . Vu que le parcours visite alternativement V0 et
V1 et revient à son point de départ, il doit suivre un nombre pair d’arêtes.
Par exemple si v0 ∈ V0 :

P arcours : v0 , v1 , v2 , ..., vn−1 v0 ⇒ n est pair.

↓ ↓ ↓ ↓ ↓
V0 , V1 , V0 , ..., V1 , V0

p arcours fermés de longueur paire =⇒ cycles de longueur paire : trivial

cycles fermés de longueur paire =⇒ biparti

Partons d’un noeud v0 arbitraire, et définissons les ensembles de noeuds

V0 = {v|d(v, v0 ) paire}
V1 = {v|d(v, v0 ) impaire}

C’est une partition des noeuds. Montrons que c’est bien une bipartition pour
le graphe.
On le montre par l’absurde. Si ce n’est pas une bipartition, on aurait par
exemple une arête entre u et v avec u, v ∈ V0 .

12
 Les plus courts chemins v0 → u et v0 → v sont de longueur paire car
u, v ∈ V0 .

Ces deux chemins ont au moins un point d’intersection (v0 lui-même) et

peut-être plusieurs. Soit w un tel point d’intersection. Alors les deux sous-
chemins de v0 vers w sont tous deux des plus courts chemins (en tant que
sous-chemins des plus courts chemins v0 → u et v0 → v) de v0 vers w, donc
de même longueur, qui est la distance d(v0 , w). Dorénavant on choisit w
comme l’intersection des deux chemins v0 → u et v0 → v qui est la plus
éloignée de v0 (voir dessin, où pcc signifie ‘plus court chemin’).

pcc v0 → u
u

v0 w

v
pcc v0 → v

Le parcours fermé wuvw (en rouge sur le dessin) est un bien un cycle, par
construction (en effet les deux chemins w → u et w → u sont sans intersec-
tion, par choix de w). On prétend qu’il est de longueur impaire. En effet, les
deux sous-chemins de v0 vers w étant de même longueur, on a :
lg(wuvw) = lg(v0 uvv0 ) − 2lg(v0 w)
impaire paire
Contradiction puisqu’on a supposé tous les cycles de longueur paire. Si
l’arête uv est dans V1 , raisonnement similaire.

13
2 Les plus courts chemins
2.1 Les plus courts chemins
Définition 2.1. Une fonction de poids sur un graphe (V , E, ϕ) est une
fonction E → R qui associe un poids réel à chaque arête du graphe. Un
graphe pondéré est un graphe muni d’une fonction de poids. Le poids ou la
longueur d’un parcours est la somme des poids des arêtes qui le compose.

Un exemple de graphe pondéré est le réseau routier belge, où les sommets

sont les villes et les arêtes les routes reliant ces villes, et auxquelles ont associe
comme poids la longueur (en kilomètres) de la route. Dans cet exemple,
comme dans beaucoup de cas pratiques, le poids des arêtes est toujours
positif.

Définition 2.2. La distance entre les noeuds u et v d’un graphe pondéré,

notée d(u, v), est la longueur du plus court chemin de u vers v, c’est-à-dire
le chemin reliant u à v de poids minimal. Attention, dans un graphe dirigé
en général d(u, v) 6= d(v, u).

Définition 2.3. Un graphe dirigé (parfois appellé digraphe) est un triplet

(V , E, ϕ), où :
— V est un ensemble dont les éléments sont appelés sommets ou noeuds ;
— E est un ensemble dont les éléments sont appelés arêtes ;
— ϕ est une fonction, dîte fonction d’incidence, qui associe à chaque
arête un couple 1 de sommets.

Exemple 2.4. Pour le graphe dirigé suivant :

a
5 1

e b
7

4 6

8 2

d 3
c

1. Dans la définition 1.1 on a parlé de paire et ici de couple car une paire est un
ensemble de 2 éléments alors qu’un couple est un n-uplet avec n = 2. Dans un ensemble,
il n’y a pas de relation d’ordre alors que dans un n-uplet, chaque élément a un indice bien
définit. Une arête est donc à sens unique dans un graphe dirigé.

14
Nous avons :

V = {a, b, c, d, e}
E = {1, 2, 3, 4, 5, 6, 7, 8}
ϕ(1) = (a, b)
ϕ(2) = (c, b)
ϕ(3) = (c, d)
ϕ(4) = (e, d)
ϕ(5) = (a, e)
ϕ(6) = (d, a)
ϕ(7) = (a, c)
ϕ(8) = (d, b)

Notons que certains résultats de la théorie des graphes non-dirigés pos-

sèdent une extension naturelle au cas dirigé. Ainsi on nomme fortement
connexe un graphe dirigé avec un parcours (au sens dirigé) de tout noeud
à tout autre. Ainsi le théorème d’Euler pour les graphes dirigés s’énonce :
un graphe fortement connexe est eulérien si et seulement si en tout noeud le
degré entrant est égal au degré sortant (avec preuve semblable). Et le théo-
rème des poignées de main : la somme des degrés entrants égale la somme
des degrés sortants, égale le nombre d’arêtes. Le cas dirigé est aussi le cadre
le plus naturel pour exprimer le problème du plus court chemin.

Théorème 2.5 (Plus court chemin et plus court parcours). Pour un graphe
(dirigé ou non) avec une fonction de poids ≥ 0, si le plus court parcours entre
u et v est de longueur d, alors le plus court chemin entre u et v est aussi de
longueur d (la notion de plus court parcours se ramène donc à celle du plus
court chemin).

Démonstration. Soit d0 la longueur du plus court chemin. Comme tout che-

min est un parcours, on a nécessairement d0 ≥ d où d est la longueur du
plus court parcours. Supposons par l’absurde que le plus court parcours soit
strictement plus court que le plus court chemin et donc que d0 > d. Ce
plus court parcours, P , n’est donc pas un chemin et contient donc un ou
plusieurs cycles. Prenons donc P = v0 . . . vi . . . vi . . . vn contenant un de ces
cycles vi . . . vi . Si on retire ce cycle vi . . . vi on obtient un nouveau parcours
P 0 = v0 . . . vi . . . vn . Comme les arêtes sont de poids positif, deux cas sont
possibles :
— Soit le cycle retiré possède au moins une arête de poids positif, donc
P 0 est plus court que P , ce qui contredit notre hypothèse que P est
le plus court parcours (impossible).
— Soit le cycle retiré est de poids nul, et P 0 a un poids d égal au poids
de P . Dans ce cas : (i) soit il n’y a plus de cycle dans P 0 , ce qui veut

15
 dire que P 0 est un chemin de longueur d inférieure à la longueur d0
du plus court chemin (impossible), (ii) soit il reste des cycles dans
P 0 , on recommence alors l’argument présenté en remplaçant P par
P 0 et on finira par tomber sur un des cas impossibles car le nombre
de cycles dans P est fini.

On se restreint donc à la notion de plus court chemin. Trouver le plus

court chemin entre deux noeuds dans un graphe est un problème impor-
tant qui nécessite un algorithme efficace (le temps de calcul nécessaire pour
essayer tous les chemins possibles est énorme).

2.2 Algorithme de Dijkstra

Algorithme 2.6 (Algorithme de Dijkstra). L’algorithme de Dijkstra prend
en entrée un graphe pondéré (connexe, dirigé ou non) G avec poids positifs,
ainsi qu’un noeud de départ u0 , et donne en sortie la distance la plus courte
entre u0 et tous les autres noeuds de G 2 . Ici, w(uv) représente le poids de
l’arête uv, S désigne l’ensemble des noeuds pour lesquels on connait la plus
petite distance depuis u0 , et `(u) est la distance la plus courte de u0 à u en
passant par les noeuds dans S uniquement. Si il n’y a pas d’arête entre u et
v on note w(uv) = ∞.
1. Initialisation :
— S = {u0 } (on connait la distance trivallement nulle au point de
départ)
— `(u0 ) = 0 et `(v) = ∞ pour v 6= u0 (`(v) est une borne supérieure
de d(u0 , v)).
— u0 = u0 (dernier noeud ajouté à S)
2. Tant qu’il reste des sommets hors de S :
— Mise à jour de ` en considérant passer par u0 : ∀v ∈ / S, `(v) ←
min(`(v), `(u0 ) + w(u0 v))
— Trouver vmin ∈ / S le plus proche : ∀v ∈
/ S, `(vmin ) ≤ `(v)
— L’ajouter à S : u0 ← vmin puis S ← S ∪ {u0 }

En d’autres mots, l’algorithme de Dijkstra ajoute à chaque itération à S

un noeud pour lequel la longueur du plus court chemin est connu, puis ré-
évalue les "plus courts chemins candidats" des noeuds restants en considérant
passer par ce nouveau noeud.

Exemple 2.7. On cherche les distances à partir de a dans le graphe suivant.

Le résultat de chaque itération de l’algorithme est notée dans une ligne du
2. Il est également possible de donner les plus courts chemins, pas uniquement leur
longueur.

16
tableau associé.

a
10 50

e b
30

10 5

20 5

d 50
c

u0 S l(a) l(b) l(c) l(d) l(e)

a {a} 0 ∞ ∞ ∞ ∞
a {a, e} 50 30 ∞ 10
e {a, e, d} 50 30 20
d {a, e, d, c} 40 30
c {a, e, d, c, b} 35

Théorème 2.8 (L’algorithme de Dijkstra fonctionne). Après chaque mise

a jour de ` dans l’algorithme, les deux propriétés suivantes 3 sont vérifiées :
— pour v ∈ S, `(v) = d(u0 , v) et le chemin le plus court de u0 à v reste
dans S ;
— pour v ∈ / S, `(v) ≥ d(u0 , v), et `(v) est la longueur du plus court
chemin de u0 vers v dont tous les noeuds internes sont dans S.

Démonstration. Faisons une preuve par induction : on suppose qu’à l’ité-

ration i − 1 les propriétés sont vérifiées et on cherche à les prouver pour
l’itération i. Soit Si l’ensemble S à la fin de l’itération i.
Initialisation Au début, `(u0 ) = 0 = d(u0 , u0 ) et `(v) = ∞ > d(u0 , v) (car
on considère le graphe connexe), les deux propriétés sont vérifiées.
Induction On prouve une propriété à la fois :
— Il faut prouver qu’après avoir ajouté un noeud ui dans Si , `(ui ) =
d(u0 , ui ) (par hypothèse d’induction, la propriété est vérifiée pour
les autres éléments de Si ). Supposons par l’absurde que `(ui ) >
d(u0 , ui ). Comme (par hypothèse d’induction sur la seconde pro-
priété) `(ui ) est la longueur du plus court chemin où tous les
noeuds intermédiaires sont dans Si−1 , la seule possibilité pour que
`(ui ) 6= d(u0 , ui ), c’est qu’il existe un plus court chemin passant par
3. Puisque ces propriétés sont vérifiées à chaque itération de la boucle, on les appelle
des invariants de boucle.

17
 un noeuds de S̄i−1 . Soit v, le premier noeud de S̄i−1 de ce chemin.
Le sous-chemin de u0 à v est le plus court chemin de u0 à v par le
lemme 1.24. Par la définition de v, ce chemin ne passe que par des
noeuds de Si−1 . Du coup, on sait que d(u0 , v) = `(v). Comme les
arêtes sont de poids positifs, on a `(v) = d(u0 , v) ≤ d(u0 , ui ). Mais
comme on a pris ui tel que `(ui ) = minu∈S̄i−1 `(u), on a `(ui ) ≤ `(v).
Dès lors `(ui ) ≤ d(u0 , ui ), ce qui est absurde car on a supposé le
contraire.
— Commençons par montrer que `(v) ≥ d(u0 , v). Les seuls, `(v) qui
changent à cette itération sont égaux à `(ui ) + w(ui , v). On re-
marque que c’est la longueur du chemin composé du plus court
chemin de u0 à ui et de l’arête de ui à v. Par la définition de
d(u0 , v), on a donc nécessairement l’inégalité voulue.
Pour le dernier point, par l’hypothèse de récurrence, on sait que
`(v) est la longueur du plus court chemin de u0 vers v pour tout
noeud de Si−1 . Pour que ce soit vrai pour tout noeud de Si , il reste
à considérer les chemin passant par ui . De tout ces chemins (de
u0 à v passant par ui et dont les noeuds internes sont dans Si ), il
ne faut garder que le chemin constitué du plus court chemin de u0
vers ui et de l’arête ui v parce que les autres chemins candidats ne
sont pas des plus courts chemins. En effet, comme ui est le dernier
noeud a avoir été ajouté à Si , ui est le noeud le plus éloigné de u0
ce qui veut dire que ui n’est jamais sur un plus court chemin vers
un noeud de Si (mis à part celui vers ui bien sûr). La longueur de
ce chemin est `(ui ) + w(ui , v). Le plus court chemin vers v passe
donc soit uniquement par Si−1 (longueur `(v) calculée à l’itération
précédente) soit le chemin passant par ui (longueur `(ui )+w(ui , v)),
ce qui correspond à la mise à jour `(v) ← min(`(v), `(ui )+w(ui , v)).

Corollaire 2.9 (L’algorithme de Dijkstra est correct). L’algorithme de

Dijkstra est correct.
Théorème 2.10 (L’algorithme de Dijkstra est quadratique). L’algorithme
de Dijkstra sur un graphe se termine en un temps de l’ordre n2 , on note que
le temps est O(n2 ).

Démonstration.
— Au début |S̄| = n − 1 et à chaque passage de boucle |S̄| décroit de 1.
Ce qui implique n itérations.
— A chaque itération, l’instruction “∀v ∈ S̄” fait O(n − |S|) opérations ;
ensuite “trouver vmin “ fait O(n − |S|) opérations également.
— Le nombre d’opérations total est donc 2n + 2(n − 1) + ... + 2(1). Cela
implique un temps total (on oublie les  constantes
 multiplicatives)
O(n + (n − 1) + (n − 2) + ... + 1) = O n(n+1)
2 = O(n 2 ).

18
 Rappelons le sens de la notation O(.). Soient deux fonctions f et g des
entiers vers les réels. On dit que f ∈ O(g) s’il y a des constantes n0 et c telles
que |f (n)| ≤ cg(n) pour tout n ≥ n0 . Par exemple 2n3 ∈ O(n3 + 10n2 ), ou
n log n ∈ On2 . On généralise aisément aux fonctions de plusieurs variables
entières, par exemple n + m ∈ Onm.
Les temps de calcul d’un algorithme sont ici toujours considérés au pire,
pour l’instance de taille donnée la plus défavorable.

Définition 2.11. Un algorithme travaillant sur un graphe G = (V, E, ϕ)

avec |V | = n, |E| = m est un algorithme efficace si il possède un temps
d’exécution borné par un polynôme, donc en O(P (n, m)) pour un certain
polynôme P . L’algorithme de Dijkstra est un exemple d’algorithme efficace,
avec P (n, m) = n2 .

2.3 Anneaux et Semi-anneaux

Définition 2.12. Un semi-anneau est un ensemble muni de deux opérations
(⊕, ⊗) et leur propriétés habituelles.

Définition 2.13. Un anneau est un ensemble muni de trois opérations

(⊕, ⊗, ) et leur propriétés habituelles.

Définition 2.14. Un corps est un ensemble muni de quatre opérations

(⊕, ⊗, , ) et leurs propriétés habituelles.

Par exemple, une de ces propriété est la distributivité :

a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c)

On peut définir une somme et un produit matriciels dont les entrées sont
dans le semi-anneau :

A ⊕ B = (aij ⊕ bij )ij (1)

X
A⊗B = ( aik ⊗ bkj )ij (2)
k

Les matrices munies de ces opérations forment à leur tour un semi-anneau.

Prenons, sur les réels (augmentés de l’infini), ⊕ = min et ⊗ = +. Le
neutre de min est ∞ et celui de + est 0 donc
 
∞ 0 ... ∞
.
∞ . . .. .
. .. 

I= . . .
 
. .. ..
. . ∞ 
∞ ... ∞ 0

19
 En prenant A tel que aij = w(i, j), en comptant w(i, j) = ∞ (longueur
infinie) partout où il n’y a pas d’arêtes, la matrice Ak a pour élément ij la
longueur du plus court parcours à k arêtes de i vers j : cela se démontre
aisément par induction sur k. Si on ajoute des boucles de poids nul sur le
graphe, autrement dit on considère la matrice de poids I ⊕A, alors (I ⊕A)⊗k
encode les plus courts chemins de longueur au plus k. Comme tout chemin
est au plus de n noeuds dans un graphe à n noeuds, la matrice des plus
courts chemins entre chaque paire de noeuds est donnée par

(I ⊕ A)⊗n .
Pour calculer cette matrice, on peut effectuer n multiplications matri-
cielles successives, chacune s’effectuant (suivant l’application naïve de la
définition) en n3 opérations. On arrive donc à n4 opérations. Plus efficace
est d’élever la matrice I ⊕ A au carré log2 n fois de suite, aboutissant ainsi à
n3 log n. C’est un peu moins bon que l’application de l’algorithme de Dijks-
tra sur chaque noeud (n3 ).
Mais le semi-anneau (min, +) possède des propriétés intéressantes, dont
l’idempotence : a ⊕ a = a pour tout a. Ces propriétés, utilisées de manière
ingénieuse, permettent de court-circuiter certains calculs de la multiplication
et d’obtenir une complexité en n3 / log n (Timothy M Chan 2005), ou même
moins. Ceci est la manière la plus efficace de calculer toutes les distances
dans un graphe.

20
3 Arbres et connectivité
Dans ce chapitre il est important de noter que tous les graphes sont
non-dirigés, pas nécessairement simples (les arêtes multiples et les boucles
sont autorisées), sauf spécification contraire. La théorie des arbres et de la
connectivité pour les graphes dirigés est beaucoup moins univoque : on peut
généraliser les concepts et résultats au cas dirigé de plusieurs manières et
ceci n’est pas traité dans ce cours.

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

Définition 3.2. Un sous-graphe sous-tendant ou couvrant d’un graphe G

est un sous-graphe qui contient tous les sommets de G.

Théorème 3.3 (Arbres sous-tendants). Tout graphe connexe contient un

arbre sous-tendant.

Démonstration. Parmi tous les sous-graphes sous-tendants connexes, on choi-

sit un sous-graphe minimal pour l’inclusion dans cet ensemble (minimal pour
l’inclusion = si j’enlève n’importe quelle arête, alors je perds la connexité).
Je prétends que c’est un arbre sous-tendant :
— Connexe : par construction
— Sans cycle : supposons un cycle. Soit e = uv une arête quelconque
de ce cycle. Si on enlève e, le graphe est toujours connexe (en effet,
pour tout parcours x → uev → y, on peut remplacer e par le reste
du cycle dont e faisait partie). Il y a contradiction, donc il n’y pas de
cycle.

Théorème 3.4 (Caractérisations des arbres). Soit G un graphe à n sommets

et m arêtes. Alors les conditions suivantes sont équivalentes :
1. G est connexe et sans cycle ;
2. G est sans cycle et m = n − 1 ;
3. G est connexe et m = n − 1 ;
4. G est connexe et supprimer une arête quelconque déconnecte G ;
5. G est sans cycle et ajouter une arête quelconque crée un et un seul
cycle ;
6. Deux noeuds de G sont toujours reliés par un seul chemin.
La dernière condition implique, appliquée pour deux noeuds identiques, que
G est sans boucle.

21
Démonstration. Nous allons démontrer que chaque condition implique la
suivante, et la dernière la première. Ainsi il sera établi qu’elles sont toutes
équivalentes.
— (1) ⇒ (2) :
Il faut juste prouver qu’un arbre (graphe connexe et sans cycle) a
m = n − 1 arêtes :
• D’abord, on prouve que tout arbre possède une feuille, càd un
nœud de degré 1. Tous les nœuds ont un degré ≥ 1 (par connexité,
s’il y a au moins deux nœuds). Supposons que tous les nœuds aient
un degré au moins 2. Alors, partant d’un nœud on peut créer un
parcours sans jamais rebrousser chemin (chaque fois qu’on visite
un nœud pour la première fois, on peut sortir par une autre arête),
jusqu’à revenir à un nœud déjà visité. Cela implique qu’on peut
extraire un cycle, d’où contradiction. Tout arbre possède donc au
moins une feuille.
• On procède par récurrence sur n. Pour n = 1, m = 0 : on a bien
m = n − 1. Pour tout arbre de n + 1 noeuds on trouve une feuille
x. En enlevant x et son arête, on obtient un nouvel arbre de n
nœuds (on a supprimé un noeud) et n − 1 arêtes (par hypothèse
de récurrence). Donc l’arbre de n + 1 nœuds avait bien n arêtes.
— (2) ⇒ (3) :
Un graphe sans cycle de m = n − 1 arêtes est-il connexe ?
Supposons qu’il y ait éventuellement plusieurs composantes connexes,
de ni nœuds et mi arêtes. Sur chacune, on peut appliquer (1) ⇒ (2)
(puisque chaque composante est connexe et sans cycle). Donc, pour
toute composante connexe i : mi = ni − 1. Sommons maintenant sur
P
l’ensemble des composantes connexes, et l’on obtient m = i mi =
i ni − #composantes connexes = n − #comp. conn. qui doit être
P

égal à n − 1 par hypothèse. Donc il n’y a qu’une seule composante

connexe.
— (3) ⇒ (4) :
Soit G un graphe connexe de m = n − 1 arêtes.
Supprimer une arête de G déconnecte-t-il le graphe ? Supposons par
l’absurde qu’en enlevant une arête e à G, le graphe résultant G − e
reste connexe. Par le théorème précédent, dans G − e (connexe), il
y a un arbre sous-tendant. Par (1) ⇒ (2), cet arbre a n − 1 arêtes.
Donc G − e a au moins n − 1 arêtes. Donc G a au moins n arêtes,
d’où contradiction avec l’hypothèse m = n − 1.
— (4) ⇒ (5) :
Soit G connexe, déconnecté par tout retrait d’une arête.
Est-il bien sans cycle ? S’il y avait un cycle, on pourrait supprimer
une arête de ce cycle et maintenir la connexité, ce qui n’est pas le cas
par hypothèse. Il n’y a donc pas de cycle.

22
 Vérifions qu’ajouter une arête quelconque crée un et un seul cycle :
• D’abord, on prouve qu’il existe un cycle. Ajoutons une arête e
entre les noeuds u et v. Par connexité, il existe un chemin C =
u . . . v. Donc u
| .{z
. . v} eu est un cycle.
C
• Ensuite, on prouve que c’est le seul cycle. Supposons qu’on ait
obtenu au moins 2 cycles C1 , C2 en ajoutant e. Alors on a un par-
cours fermé u . . . v . . . u dans G (en adjoignant C1 − e à C2 − e),
dont on peut extraire un cycle dans G, ce qui est une contradic-
tion.
— (5) ⇒ (6) :
Soit G sans cycle et muni d’un et un seul cycle par tout ajout d’arête.
Soit deux nœuds u et v. Supposons qu’il existe deux chemins P1 =
u . . . v, P2 = u . . . v, alors u . . . v . . . u est un parcours fermé dont on
peut extraire un cycle, contradiction. Il y a donc au plus un chemin
u → v. En ajoutant une arête e entre u et v, par hypothèse je crée un
cycle C. Cela implique que C − e est un chemin u → v. Il y a donc
bien un chemin entre deux noeuds de G et c’est le seul.
— (6) ⇒ (1) :
Soit G un graphe qui trace un et un seul chemin entre toute paire de
noeuds. Il est donc connexe. Est-il sans cycle ? Supposons qu’il existe
un cycle. Soient x et y deux nœuds distincts dans ce cycle. Le cycle
donne deux chemins x → y, en contradiction avec l’hypothèse. Il n’y
a donc pas de cycle.

Définition 3.5. Soit G = (V, E, ϕ) un graphe et soit e = (u, v) une arête

de G. On définit les opérations suivantes sur G :
— Suppression d’arête. On définit G − e = (V, E\{e}, ϕ) comme le
graphe obtenu en supprimant l’arête e de G.
— Contraction d’arête. On définit G.e = (V \{u, v} ∪ {w}, E\{e}, ϕ0 )
comme le graphe obtenu en contractant l’arête e de G, où ϕ0 est
obtenu à partir de ϕ en remplaçant chaque occurrence des sommets u
et v par w. En d’autres termes, les sommets u et v sont remplacés par
un sommet w qui reprend toutes leurs arêtes initiales, à l’exception
de e qui est retirée du graphe.

Théorème 3.6 (Formule de Cayley). Soit T (G) le nombre d’arbres sous-

tendants de G, et e une arête quelconque de G, qui n’est pas une boucle.
Alors T (G) = T (G − e) + T (G.e).

Démonstration. On divise les arbres sous-tendants de G en deux catégories

a) ceux qui ne contiennent pas l’arête e ;
b) ceux qui contiennent l’arête e.

23
On compte chaque catégorie :
— On voit que les arbres de a) sont en bijection avec les arbres sous-
tendants de G−e. En effet un arbre sous-tendant de G qui ne contient
pas e reste un arbre sous-tendant de G − e et inversément.
— On voit que les arbres de b) sont en bijection avec les arbres sous-
tendants de G.e. L’argument est similaire : tout arbre A sous-tendant
de G qui contient e engendre un arbre A.e sous-tendant de G.e et ré-
ciproquement, tout arbre sous-tendant de G.e correspond à un arbre
sous-tendant de G qui contient e.
On a donc T (G) = T (G − e) + T (G.e).

Le théorème suivant est admis sans démonstration :

Théorème 3.7 (Théorème de Cayley). Le nombre d’arbres sous-tendants

du graphe complet à n noeuds est nn−2 .

Exemple 3.8 (Application de la formule de Cayley).

T( ) = T( ) + T( )
= T( ) + T( ) + T( ) + T( )
= 1 + T( ) + T( ) + T( ) + T( ) + 2
=1+1+2+1+1+2
= 8.

On notera que la contraction génère quelque fois des boucles, qui n’ont pas
été représentées ici car elles n’interviennent dans aucun arbre.

3.2 Arbre sous-tendant de poids minimum

Un problème courant concernant les arbres est le calcul de l’arbre sous-
tendant de poids minimum dans un graphe connexe. Si tous les poids sont
positifs, cela revient à chercher le sous-graphe sous-tendant de poids mini-
mum. Par exemple, on pourrait chercher le réseau téléphonique le moins
cher possible permettant de connecter une série de stations.
L’algorithme de Kruskal (1956), 3.9 ci-dessous, permet de calculer effi-
cacement cet arbre. Cet algorithme d’une simplicité surprenante car il s’agit
d’un algorithme glouton, c’est-à-dire qui opère une série de choix basés l’im-
pact immédiat sur la fonction objective, sans jamais les remettre en cause.
A chaque étape, l’algorithme considère l’arête la moins chère non-encore ex-
plorée. Si cette arête ne crée pas de cycle avec les arêtes déjà choisies, celle-ci
est définitivement ajoutée à l’arbre en construction.

Exemple 3.10 (Exécution de l’algorithme de Kruskal). On cherche l’arbre

sous-tendant de poids minimum de :

24
Algorithme 3.9 (Algorithme de Kruskal).
#Entrée : graphe connexe pondéré
#Sortie : T , arbre sous-tendant de poids minimum

Etrié ← E trié en ordre croissant

while |T | < |V | − 1 [#Invariant : T est une forêt] do
e ← première arête de Es
Etrié ← Etrié \ {e}
if e ne crée pas de cycle then
T ← T ∪ {e}
end if
end while

On montre à présent que malgré sa simplicité, l’algorithme de Kruskal

fournit toujours un arbre de recouvrement de poids minimal.
Prouvons d’abord un petit lemme qui encapsule l’argument fondamen-
tal de la preuve de correction de l’algorithme de Kruskal, mais aussi de
l’algorithme de Prim, expliqué juste après.

Lemme 3.11. Soit F un ensemble d’arêtes du graphe connexe pondéré G,

qui peut être étendu en un arbre sous-tendant de poids minimum (autrement
il y a un abre sous-tendant de poids minimum qui contient F , en particulier
F est une forêt). Soit encore une partition des noeuds V en plusieurs classes
non vides V1 , V2 , . . ., et C la coupe d’arêtes associée — c.-à-d. l’ensemble des
arêtes entre deux classes Vi et Vj différentes — que l’on suppose disjointe
de F . Soit encore e ∈ C une arête de poids minimum parmi les arêtes de C.
Alors F ∪ {e} peut également être étendu en un arbre sous-tendant de poids
minimum.

25
Démonstration. Soit T un arbre sous-tendant de poids minimum qui contient
F . Si e ∈ T alors la conclusion est trivialement vraie : F ∪ {e} est étendue
par T . Si e ∈/ T alors je considère T + e, qui possède un unique cycle. Ce
cycle passe nécessairement par une arête (au moins, en plus de e) de C qui
relie deux composantes connexes de G − C, puisqu’il relie une extrémité de
e qui est dans V1 à l’autre extrémité, qui est dans V2 . Soit f ∈ C une telle
arête. On voit que T + e − f , qui n’a plus de cycle (en enlevant f on brise
l’unique cycle de T + e) et a le même nombre d’arêtes que T , est également
un arbre sous-tendant. Puisque e est de poids w(e) ≤ w(f ) (par définition
de e ; on note w(.) la fonction de poids), et que w(T ) ≤ w(T + e − f ) (par dé-
finition de T , de poids minimum), on a que w(e) = w(f ). Donc T + e − f est
également un arbre sous-tendant de poids minimum, qui étend F ∪ {e}.

Théorème 3.12. L’algorithme de Kruskal est correct.

Démonstration. On démontre par induction qu’à tout moment l’ensemble

des arêtes découvertes peut être étendu en un arbre sous-tendant de poids
minimum du graphe connexe pondéré G sur lequel on applique l’algorithme.
C’est trivialement le cas au début de l’algorithme, quand l’ensemble des
arêtes découvertes est vide. Ensuite, tant que les arêtes découvertes ne
forment pas un arbre sous-tendant, on applique le lemme 3.11 ci-dessus,
avec F l’ensemble de tous les noeuds du graphe et des arêtes découvertes, et
C l’ensemble des arêtes du graphe qui relient deux arbres de F (les classes
de noeuds Vi sont donc les composantes connexes de F ). L’algorithme ajoute
alors l’arête e de poids minimum de C qui relie deux composantes connexes
de F . Le nouvel ensemble d’arêtes découvertes peut donc bien être étendu
en un arbre sous-tendant de poids minimal. A la dernière étape, on a donc
bien un arbre sous-tendant de poids minimal.

Théorème 3.13 (L’algorithme de Kruskal est efficace). L’algorithme de

Kruskal requiert un temps de calcul de l’ordre de O(m log(m)) sur un graphe
à m arêtes.

Démonstration. On doit commencer par trier les arêtes du graphe ce qui se

fait en O(m log(m)) avec un algorithme efficace.
Savoir si ajouter une arête crée un cycle se fait en O(log(m)), et même
beaucoup moins en moyenne, à condition d’utiliser la bonne structure de
données pour retenir les arêtes déjà sélectionnées par l’algorithme. Quoique
la description complète dépasse le cadre de ce cours, on peut en donner ici
une description générale à toutes fins pratiques. A tout moment l’ensemble
des arêtes déjà sélectionnées est une forêt. On retient pour chaque noeud
dans quelle composante connexe de la forêt il se trouve. Une arête crée un
cycle si et seulement si ses deux extrémités sont dans la même composante
connexe, il faut donc être capable de trouver (‘Find’) rapidement dans quelle
composante connexe ces deux noeuds se trouvent. Si une arête joint deux

26
composantes connexes différentes, alors on admet l’arête et on fusionne les
deux composantes connexes en une seule (‘Union’).
On utilise donc une structure de données dite ‘Union-Find’ (ou ‘en-
sembles disjoints’, car les éléments sont répartis en ensemble disjoints). C’est
une structure de donnée qui enregistre une partition d’un ensemble donné.
Les classes de la partition sont désignées par un représentant de la classe
(élément arbitrairement choisi pour jouer ce rôle). Une opération de base
est la fusion de deux classes en une seule (Union). Une autre est de vérifier à
quelle classe appartient un élément donné (Find). Une troisième consiste à
ajouter un nouvel élément à l’ensemble, qui forme sa propre classe-singleton
(MakeSet).
Ici, à partir d’une structure de données vide, on peut créer une partition
de tous les noeuds en autant de classes-singletons (n opérations MakeSet) ; à
tout moment de l’algorithme, les classes de la partition encodent les noeuds
reliés par un même arbre. Ensuite pour vérifier si une arête doit être ajoutée,
on vérifie comme on a dit si les deux extrémités appartiennent au même
arbre (deux opérations Find). Si on ajoute l’arête à la forêt, on fusionne les
classes contenant les noeuds présents dans les arbres reliés par cette arête
(une opération Union).
Quelle est la complexité de ces opérations ? Par une implémentation astu-
cieuse de ces opérations, une suite des N opérations élémentaires en partant
d’une structure vide peut être effectuées en temps N O(α(N )). Ici la fonction
α(N ) est une fonction qui croît indéfiniment en fonction de N bien plus len-
tement que log N , en fait si lentement qu’on peut considérer qu’en pratique
elle est bornée par 5, par exemple. Pour l’anecdote c’est la réciproque de la
fonction f (n) = A(n, n) d’Ackermann, construite par ce dernier pour donner
un exemple de fonction de croissance extrêmement rapide. Dans notre cas,
on vérifie donc que la difficulté principale de l’algorithme est la phase de tri
des arêtes.
Mentionnons encore l’algorithme de Prim (1957) fait croître un arbre
(non-sous-tendant, sauf à la dernière étape) de proche en proche à partir
d’un noeud arbitraire, en ajoutant toujours l’arête la plus légère pour ce
faire, jusqu’à atteindre tous les noeuds.

Exemple 3.15 (Exécution de l’algorithme de Prim). On cherche l’arbre

sous-tendant de poids minimum de :
5 5 5
11 11 11
6 4 6 4 6 4
8 8 8
12 12 12
10 10 10
9 9 9
7 7 7
3 2 3 2 3 2

27
Algorithme 3.14 (Algorithme de Prim).
#Entrée : un graphe connexe pondéré
#Sortie : T un arbre sous-tendant de poids minimum

T ← noeud arbitraire et pas d’arête

while T non-sous-tendant [#Invariant : T est un arbre] do
e ← arête la plus légère avec exactement une extrémité dans T
x ← extrémité de e qui n’est pas dans T
T ← x et e
end while

5 5 5
11 11 11
6 4 6 4 6 4
8 8 8
12 12 12
10 10 10
9 9 9
7 7 7
3 2 3 2 3 2

On voit sans peine qu’à la sortie de l’algorithme l’ensemble de noeud et

d’arêtes T est bel et bien un arbre sous-tendant. Qu’il soit bien de poids
minimal se prouve de façon très semblable à l’algorithme de Kruskal, en
utilisant le lemme ci-dessus.
Théorème 3.16. L’algorithme de Prim est correct.

Démonstration. On démontre par induction qu’à tout moment l’ensemble

des arêtes découvertes peut être étendu en un arbre sous-tendant de poids
minimum du graphe connexe pondéré G sur lequel on applique l’algorithme.
C’est trivialement le cas au début de l’algorithme, quand l’ensemble des
arêtes découvertes est vide. Ensuite, tant que les arêtes découvertes ne
forment pas un arbre sous-tendant, on applique le lemme 3.11, avec F l’en-
semble des arêtes découvertes et les noeuds incidents (qui forment un arbre
non-sous-tendant), et C l’ensemble des arêtes du graphe qui ont exactement
une extrémité incidente à F (donc V1 est la classe des noeuds déjà découverts
et V2 les autres noeuds du graphe). Alors l’algorithme ajoute précisément
l’arête de C la plus légère à F , formant ainsi un nouvel arbre qui peut être
étendu à un arbre sous-tendant de poids minimum. A la fin, on a donc bien
un arbre sous-tendant de poids minimum.

Quant à la complexité, elle dépend de l’implémentation. Une implémen-

tation adéquate requiert la structure de données dite “file de priorité” pour
encoder les noeuds et trouver commodément le prochain noeud à ajouter
au graphe. Une file de priorité peut elle même être implémentée de fa-
çons diverses : avec un “tas de Fibonacci” on atteint une complexité de

28
O(m + n log n), pour un graphe de m arêtes et n noeuds. C’est mieux que
l’algorithme de Kruskal, néanmoins avec une important constante cachée,
qui est le talon d’Achille des tas de Fibonacci. Avec un “tas binaire” (qui
intervient également dans le célèbre “tri par tas”) on obtient O(m log n) ce
qui est théoriquement moins bon que le tas de Fibonacci pour des graphes
denses, et essentiellement équivalent à la complexité de l’algorithme de Krus-
kal.
Il y a encore d’autres algorithmes de recherche d’arbre sous-tendant de
poids minimal. Citons le plus ancien : celui de Borůvka (1926), et un des
plus récents : celui de Chazelle (2000), qui fonctionne en temps quasi-linéaire
O(mα(m)) (voir la preuve de complexité de l’algorithme de Kruskal pour
l’explication de α(m)).
Citons encore le théorème suivant pour vérifier qu’un arbre sous-tendant
donné est de poids minimum.

Théorème 3.17. Soit T un arbre sous-tendant d’un graphe connexe pon-

déré. Alors T est un arbre sous-tendant de poids minimum si et seulement
si toute arête e qui n’est pas dans T est au moins aussi lourde que chaque
arête de l’unique cycle de T + e.

Démonstration. =⇒ Nous supposons, par contraposition, que la conclusion

n’est pas vérifiée : il existe une arête e hors de l’arbre sous-tendant T , et
une arête e0 de T qui est sur le cycle unique de T + e (autrement dit, sur le
chemin unique de T qui rejoint les extrémités de e) telle que w(e) < w(e0 )
(où w(.) désigne la fonction de poids). Alors T + e − e0 est encore un arbre
sous-tendant (en effet retirer e0 de T + E brise l’unique cycle de T + e et
a le même nombre d’arêtes que T , on a donc bien un arbre sous-tendant),
et il est de poids w(T ) + w(e) − w(e0 ) < w(T ). Donc T n’est pas de poids
minimum.
⇐= Nous supposons, par contraposition, que T n’est pas de poids mini-
mum. Quoique T ne soit pas de poids minimum, certaines sous-forêts sous-
tendantes de T , couvrant l’ensemble des noeuds de façon non-connexe, sont
extensibles à un arbre sous-tendant de poids minimum. Par exemple il en
va ainsi de la sous-forêt à 0 arête, composée de tous les noeuds du graphe
isolés. On prend T0 un élément maximum (pour la relation de sous-graphe)
de cette famille. Autrement dit, T0 est une forêt qui peut être étendu à un
arbre sous-tendant de poids minimum, mais ce n’est pas le cas pour T0 + f ,
quelle que soit l’arête f ∈ T \ T0 .
On applique à présent le lemme 3.11, pour la forêt F = T0 , et la coupe
d’arêtes C composée de toutes les arêtes qui rejoignent deux arbres de F .
Par le lemme, pour toute arête parmi les plus légères de C, T0 + e peut
être étendu en un arbre sous-tendant T ∗ de poids minimum. On en déduit
aussi qu’aucune de ces arêtes les plus légères n’est dans T , par définition de
T0 .

29
 On peut alors considérer T + e, qui possède un cycle qui doit contenir
une arête f (autre que e) passant par deux arbres de T0 . Cette arête f ∈ T
est strictement plus lourde que e, on l’a vu. Ceci contredit la conclusion. On
a bien démontré l’implication, par contraposition.

En exploitant ce théorème, il est possible de vérifier en temps linéaire

O(m) qu’un arbre sous-tendant donné est bien de poids minimum (Dixon-
Rauch-Tarjan 1992, King 1995).

3.3 Connectivité
Les arbres sont typiquement les graphes connexes les moins résistants à la
suppression d’arête ou de sommets dans la mesure où quelle que soit l’arête
ou le sommet (de degré au moins deux) que l’on supprimme, on déconnecte
le graphe. La notion de connexité permet de définir la robustesse d’un graphe
à ce type d’opérations. Voyons à présent comment elle se formalise.

Définition 3.18. Pour un graphe connexe, une coupe de sommets est un

ensemble de sommets qui déconnecte le graphe quand on l’en retire.

Définition 3.19. Pour un graphe connexe, une coupe d’arêtes est un en-
semble d’arêtes qui déconnecte le graphe quand on l’en retire.

Définition 3.20. Un graphe est dit k-connexe s’il possède au moins k + 1

noeuds et retirer k − 1 noeuds quelconques laisse le graphe connexe ; autre-
ment dit, si toutes les coupes de sommets sont de taille au moins k.

Définition 3.21. La connectivité d’un graphe est la taille de la plus petite

coupe de sommets. Si tous les n noeuds sont voisins deux à deux (ex., le
graphe complet), la connectivité est définie comme n − 1.

Notons que le graphe complet est le seul graphe simple dont tous les
noeuds sont voisins deux à deux ; la définition s’applique aussi aux graphes
non simples.

Définition 3.22. Un graphe est dit k-arête-connexe si son arête-connectivité

est d’au moins k ; autrement dit, si retirer k − 1 arêtes quelconques laisse le
graphe connexe.

Définition 3.23. L’arête-connectivité d’un graphe est la taille de la plus

petite coupe d’arêtes.

Théorème 3.24 (Whitney 1932).

connectivité ≤ arête-connectivité ≤ degré minimum

30
Démonstration.

arête-connectivité ≤ degré minimum

Une façon de déconnecter un graphe est de retirer les arêtes incidentes au

noeud de degré minimum.

connectivité ≤ arête-connectivité
Soit S une coupe minimum de k arêtes, qui sépare les noeuds en deux en-
sembles V1 et V2 . Epuisons tous les cas possibles :
— S’il y a un noeud v1 ∈ V1 qui n’est pas incident à S, alors je peux
retirer toutes les extrémités de S dans V1 (il y en a au plus k), ce qui
déconnecte v1 de V2 : on a donc trouvé une coupe de k noeuds ou
moins.
— De même s’il y a un noeud v2 ∈ V2 qui n’est pas incident à S.
— Si au contraire S atteint tous les noeuds du graphe alors on prend
un noeud arbitraire v1 ∈ V1 . S’il est incident à (disons) d arêtes de
S, alors il y a au plus k − d autres noeuds dans V1 , atteints par les
k − d arêtes de S qui ne sont pas incidentes à v1 . Le nombre total de
voisins de v1 (dans V2 et dans V1 ) est donc au plus d + (k − d) = k.
Si v1 et ses voisins ne constituent tout le graphe alors il y a noeud v2
non voisin de v1 , et supprimer ces k voisins au plus isole donc v1 de
v2 : on a trouvé une coupe de noeuds de k noeuds au plus.
Si v1 et ses voisins ne constituent tout le graphe, alors on applique
l’argument ci-dessus à un autre noeud qui n’est pas voisin de tous
les noeuds du graphe. Si un tel noeud n’existe pas, alors tous les
noeuds (au plus k + 1) sont voisins les uns des autres : dans ce cas
par convention la connectivité est au plus k. On a bien couvert toutes
les situations possibles.

On fait à présent le lien entre la connectivité et l’existence de multiples

chemins entre chaque paire de noeuds. On commence par une version par-
ticulière du théorème de Menger pour lequel il existe une jolie preuve par
induction.

Théorème 3.25. Un graphe à au moins trois noeuds est 2-connexe ssi

toute paire de noeuds distincts est reliée par au moins deux chemins dont
les noeuds internes sont distincts.

Démonstration. ⇐= Si je retire un noeud quelconque du graphe, pour

toute paire de noeuds u, v au plus un des deux chemins joignant u à
v est affecté donc G reste connexe.

31
 =⇒ Il faut trouver deux chemins disjoints par les noeuds entre toute
paire de noeuds distincts u, v. On procède par induction sur la dis-
tance (nombre d’arêtes du plus court chemin) d(u, v) entre les deux
noeuds :
— Cas de base : d(u, v) = 1, càd u et v sont adjacents. Ici on a un
chemin trivial, composé d’une seule arête e entre u et v. Ce chemin
n’a pas de noeud intérieur, donc il suffit à présent de vérifier qu’il
existe un autre chemin. Si G est 2-connexe alors G est 2-arête-
connexe (cf. théorème précédent) donc retirer une arête laisse le
graphe connexe. En particulier si je retire l’arête e (le premier
chemin entre u et v), il reste un second chemin entre u et v.
— Si la conclusion recherchée est vraie pour toute paire de noeuds
x, y tels que d(x, y) < d(u, v), prouvons qu’elle est également vraie
pour u et v. Soit w, le dernier noeud sur le plus court chemin de
u à v. Par hypothèse, d(u, w) < d(u, v) et par récurrence, u et
w sont reliés par au moins 2 chemins dont les noeuds internes
sont distincts, nommons-les P1 et P2 . Si je retire w, il existe, par
2-connexité, un chemin P de u à v qui ne passe donc pas par
w. Soit x le dernier noeud de P qui appartient à P1 ou à P2
(éventuellement, x = u). Disons que x se trouve en fait sur P1 . Il
existe donc 2 chemins de u à v : uQ1 xQ (où Q1 est le morceau de
P1 qui va de u à x, et Q est le morceau de P qui va de x à v) , et
uP2 wv. Par construction, ces chemins sont disjoints.

Ce théorème se généralise :

Théorème 3.26 (Théorème de Menger, 1927). Un graphe à au moins k + 1

noeuds est k-connexe ssi toute paire de noeuds distincts est reliée par au
moins k chemins dont les noeuds internes sont distincts.

Nous acceptons ce théorème sans preuve mais on peut dire qu’une preuve
possible passe par la version de ce théorème pour les arêtes.

Théorème 3.27 (Théorème de Menger pour les arêtes, 1927). Un graphe à

au moins k +1 noeuds est k-arête-connexe ssi toute paire de noeuds distincts
est reliée par au moins k chemins dont les arêtes sont distinctes.

Ce théorème s’appuie lui-même sur le théorème d’égalité entre flot maxi-

mum et coupe minimum, démontré dans un autre chapitre. En réalité il
le précède historiquement, et le théorème sur flot et coupe s’est construit
comme une généralisation de celui de Menger pour les arêtes.

Théorème 3.28 (Nombre d’arêtes dans un graphe k-connexe). Tout graphe

k-connexe à n noeuds possède kn/2 arêtes au moins (condition nécessaire).

32
Démonstration. k-connexe ⇒ degré min ≥ k ⇒ degrés ≥ kn ⇒ #arêtes ≥
P

kn/2.

Il existe une famille de graphes qui atteint cette borne : les graphes de
Harary.

Théorème 3.29 (Théorème de Harary). Le graphe de Harary Hk,n (pour k

pair) possède kn/2 arêtes et est k-connexe. Ce graphe à n noeuds v0 , . . . vn−1
est défini comme celui qui relie vj à vj+1 , ..., vj+k/2 et à vj−1 , ..., vj−k/2 , où
les indices sont compris modulo n.

La construction existe aussi pour k impair, mais est plus compliquée.

Exemple 3.30. Le graphe de Harary H4,8 de degré 4 a 16 arêtes et est

4-connexe :

7 1

6 2

5 3

33
4 Graphes hamiltoniens
Définition 4.1. Un chemin est hamiltonien s’il passe par chaque noeud du
graphe une et une seule fois.

Définition 4.2. Un cycle est hamiltonien s’il passe par chaque noeud du
graphe une et une seule fois.

Définition 4.3. Un graphe est hamiltonien s’il possède un cycle hamilto-

nien.

Théorème 4.4 (Condition nécessaire pour un graphe hamiltonien). Si on

ôte k noeuds quelconques d’un graphe hamiltonien, on obtient au plus k
composantes connexes.

Démonstration. Soit v1 ...vn v1 , le cycle hamiltonien.

Retirer k noeuds du cycle casse le cycle en au plus k chemins, et tous les
noeuds sur un même chemin sont dans une même composante connexe.

Exemple 4.5. Le graphe suivant est bien hamiltonien.

(a) (b)

En retirant 3 noeuds du graphe g on obtient bien 3 composantes connexes

dans le graphe h.
Par contre, ce graphe n’est pas hamiltonien. Pour le prouver, il suffit de
supprimer les trois noeuds connectés au noeud central : on crée ainsi quatre
composantes connexes. Par le théorème précédent, cela conclut la preuve.

Théorème 4.6 (Condition suffisante pour un graphe hamiltonien, Dirac

1952). Un graphe simple à n ≥ 3 noeuds tel que le degré minimum est d’au
moins n/2 est hamiltonien.

Démonstration. Par l’absurde, supposons qu’il existe un graphe simple à

n ≥ 3 noeuds de degré minimum d(v) ≥ n2 non hamiltonien.
Prenons un tel graphe qui est maximal pour cette propriété, c’est-à-dire
qu’ajouter n’importe quelle arête dans ce graphe le rendrait hamiltonien.

34
 (c) (d)

Ce graphe G n’est pas le graphe complet Kn , donc on peut trouver des

noeuds, disons v1 et vn , non-adjacents. Comme ajouter l’arête v1 vn crée un
cycle hamiltonien (par propriété de maximalité), passant forcément par la
nouvelle arête, il existe un chemin hamiltonien d’extrémité v1 et vn obtenu
en retirant la nouvelle arête v1 vn . Disons que ce chemin est v1 v2 . . . vn−1 vn .
Considérons les ensembles :
n
S = {vi | vi+1 est adjacent à v1 } |S| = degré(v1 ) ≥
2
n
T = {vi | vi est adjacent à vn } |T | = degré(vn ) ≥
2
On sait que vn 6∈ S, par hypothèse v1 et vn ne sont pas adjacents, et vn 6∈ T .
On a donc |S ∪ T | < n puisqu’aucun des ensembles ne contient vn .
De plus, S ∩ T = ∅ : en effet, si ∃vi ∈ S ∩ T , alors v1 v2 ...vi vn vn−1 ...vi+1 v1
est un cycle hamiltonien.

vi+1 vn−1 vn

v1 v2 vi

Enfin, |S ∪ T | = |S| + |T | − |S ∩ T | ≥ n mais |S ∪ T | < n : on a notre

contradiction !

Un problème particulièrement courant faisant intervenir les cycles ha-

miltonien est celui du voyageur de commerce.

Définition 4.7 (Problème du voyageur de commerce). Dans un graphe pon-

déré, trouver le parcours fermé le plus court qui passe par tous les noeuds
au moins une fois.

L’analogue pour des arêtes se nomme le problème du postier chinois.

Définition 4.8 (Problème du postier chinois). Dans un graphe pondéré,

trouver le parcours fermé le plus court qui passe par toutes les arêtes au
moins une fois.

35
 Notons qu’on connaît un algorithme efficace (en temps polynomial) pour
résoudre le problème du postier chinois, mais pas pour celui du voyageur de
commerce. . .

36
5 Mariages, couplages et couvertures
5.1 Couplage
Définition 5.1. Un couplage dans un graphe est un ensemble d’arêtes M
tel que M ne contient pas de boucles et deux arêtes de M n’ont jamais
d’extrémité en commun.

Définition 5.2. Un couplage maximum est un couplage dont le nombre

d’arêtes est maximal.

Définition 5.3. Un couplage parfait est un couplage qui est incident à tous
les noeuds.

Remarque 5.4. Un couplage parfait, s’il existe, est maximum.

Définition 5.5. Pour un couplage M , un chemin M-alterné est un chemin

qui passe alternativement par une arête de M et par une arête hors de M .

Définition 5.6. Un chemin M-augmenté est un chemin M-alterné dont les

noeuds d’origine et de destination ne sont incidents à aucune arête de M .

Théorème 5.7 (Berge). Un couplage M est maximum si et seulement s’il

n’y a pas de chemin M -augmenté.

Démonstration. Preuve : =⇒ On montre la contraposée, qui s’énonce : s’il

y a un chemin M -augmenté, alors M n’est pas maximum. Soit le couplage
M , représenté en bleu sur la figure ci-dessous, et un chemin M -augmenté en
vert que nous noterons P . Il faut donc montrer que M n’est pas maximum.

On construit l’ensemble d’arêtes M 0 = M ∆P où ∆ indique une différence

symétrique entre M et P (par définition, M ∆P = (M \P ) ∪ (P \M ) indique
la différence symétrique, ce sont donc les arêtes qui appartiennent à M ou
à P mais pas aux deux). On vérifie aisément que M 0 est bien un couplage :
tous les noeuds incidents à une arête de M sont incidents à une (et une
seule) arête de M 0 , et les deux extrêmités de P , qui n’étaient pas incidentes
à M , sont maintenant chacune incidente à une arête de M 0 . Ce nouveau
couplage est représenté en rouge. |M 0 | = |M | + 1. On voit bien que M n’est
pas maximum.

37
 ⇐= On procède à nouveau par contraposition : on montre que si M
(représenté en bleu ci-dessous) n’est pas maximum, alors il y a un chemin
M -augmenté. Soit M ∗ le couplage maximum (en rouge), avec |M ∗ | > |M |.
On va construire un chemin M -augmenté.

Regardons M ∆M ∗ , qui est composé des arêtes appartenant à M ou

M ∗ mais pas les deux. Précisons tout de suite qu’en dehors de M ∆M ∗ ,
les couplages M et M ∗ coincident, par définition de M ∆M ∗ . Donc dans
M ∆M ∗ , il y a strictement plus d’arêtes de M ∗ que d’arêtes de M .

On observe en outre que les noeuds dans M ∆M ∗ sont de degré 0, 1 ou

2. Les noeuds de degrés 2 ont une arête dans M et une arête dans M ∗ .
Donc M ∆M ∗ est une union de noeuds isolés, chemins et cycles ; de plus les
chemins et les cycles alternent les arêtes de M et les arêtes de M 0 . Les cycles
sont par conséquent de longueur paire, et comptent autant d’arêtes de M
que de M ∗ . Il faut qu’il existe un chemin de longueur impaire qui commence
et termine par une arête de M ∗ . On voit facilement que ce chemin est un
chemin M -augmenté. En effet chaque extrêmité de ce chemin est incidente
à M 0 , donc n’est pas incidente à d’autre arête de M 0 (un couplage) dans le
graphe, et donc n’est pas incidente à une arête de M , ni dans M ∆M 0 (par
choix du chemin), ni en dehors de M ∆M 0 (où M et M 0 coïncident).

Théorème 5.8 (Théorème du mariage ou de Hall). Un graphe biparti avec

bipartition (X, Y ) possède un couplage incident à tous les noeuds de X si
et seulement si pour tout ensemble S ⊆ X, le nombre de voisins de S est au
moins |S|.

Démonstration. Montrons les deux sens, l’un après l’autre.

38
=⇒ Un couplage M incident à tout x ∈ X crée une fonction injective
fM : X → Y : x 7→ y où y est le noeud associé à x dans le couplage M .
On a ∀S ⊆ X, fM (S) ⊆ Voisin(S). Dès lors, | Voisin(S)| ≥ |fM (S)| =
|S|.
⇐= Par contraposition, on suppose qu’il n’existe pas de couplage inci-
dent à tout X et on veut montrer qu’il existe un S ⊆ X : | Voisin(S)| <
|S|.
Soit M le couplage maximum (en vert sur la figure ci-dessous) et
u ∈ X non incident à M . Prenons les chemins M alternés partant
de u : Soit Z l’ensemble des noeuds ainsi rencontrés. S = X ∩ Z,
T = Y ∩ Z. Notons que ces chemins M -alternés quittent toujours T
vers S par une arête de M , et quittent toujours S vers T par une
arête hors M .
On remarque que
— Voisin(S) = T (par construction ; une arête entre S et Y \ T
ne peut être dans le couplage, et si elle est hors couplage elle
constituerait un moyen de prolonger un chemin M -alterné, donc
l’extrêmité côté Y serait dans T également) ;
— M est incident à tout T , sinon on aurait un chemin M -augmenté
— car un chemin alterné qui part de u et qui arrive finalement à
y ∈ T (via une arête hors M ) peut toujours poursuivre par une
arête de M , si M est bien incident à T , mais doit s’arrêter à y et
constituer un chemin M -augmenté si M n’est pas incident à y ;
— M est incident à tout S\{u} par construction ;
— M crée une bijection entre S\{u} et T — car fM (S \ {u}) ⊆ T
et fM (T ) ⊆ S \ {u}, où l’on se rappelle que fM est injective.
On a dès lors Voisin(S) = T d’où | Voisin(S)| = |S| − 1 < |S|.

39
 u

S
T

X \S
Y \T

Définition 5.9. Un graphe est k-régulier si tous les noeuds sont de degré
k.

Corollaire 5.10 (du théorème de Hall). Tout graphe biparti k-régulier

(pour k > 0) possède un couplage parfait.

Démonstration. Soit (X, Y ) la bipartition d’un graphe biparti k-régulier. Le

|)k
nombre d’arêtes est par le théorème des poignées de main (|X|+|Y 2 mais
aussi |X|k (en comptant les arêtes incidentes à X, et elles le sont toutes
bien sûr) et |Y |k (arêtes incidentes à Y ). Donc on voit que |X| = |Y |, pour
k > 0.
Soit un ensemble S ⊆ X quelconque, on définit
— E1 = {arêtes incidentes à S}
— E2 = {arêtes incidentes à Voisin(S)}
On remarque
— E1 ⊆ E2 ,
— |E1 | = |S|k,
— |E2 | = | Voisin(S)|k,
donc |S| ≤ | Voisin(S)|
Donc le théorème de Hall s’applique : il existe un couplage incident à
tout X. Ce couplage est parfait car |X| = |Y |.

5.2 Couverture
Définition 5.11. Une couverture de sommets d’un graphe est un ensemble
de sommets incident à toutes les arêtes.

40
Définition 5.12. Une couverture de sommets minimum d’un graphe est
une couverture de sommets avec un nombre minimal de sommets.

Lemme 5.13. Si K est une couverture de sommets et M un couplage, alors

|M | ≤ |K|.

Démonstration. Toute arête a une extrémité dans K, par définition de cou-

verture de sommets. En particulier toute arête m de M a une extrémité
xm ∈ K (si les deux extrémités de m sont dans K alors on nomme l’une
d’elles xm , au choix). L’application M → K : m 7→ xm est injective, par la
définition de couplage. Donc |M | ≤ |K|.

Lemme 5.14. Si K est une couverture de sommets, M un couplage et que

|M | = |K|, alors K est minimum et M est maximum.

Démonstration. Soit M ∗ un couplage maximum et K ∗ une couverture mi-

nimum. Donc par le résultat précédent, |M ∗ | ≤ |K ∗ |. En fait on peut
écrire |M | ≤ |M ∗ | ≤ |K ∗ | ≤ |K|. Par conséquent, si |M | = |K| alors
|M | = |M ∗ | = |K ∗ | = |K|.

Notons que le lemme fournit une condition suffisante et pas nécessaire.

Par exemple, dans le graphe suivant, les noeuds indiqués en rouge forment
couverture de sommets minimum K et les arêtes indiquées en bleu forment
un couplage maximum M , or |K| = 6 |M |.

Théorème 5.15 (König). Dans un graphe biparti, si K ∗ est une couverture

de sommets minimum et M ∗ un couplage maximum, alors |M ∗ | = |K ∗ |.

Démonstration. La preuve suit de très près les idées de la preuve du théo-

rème de Hall ci-dessus. Soit un graphe biparti de bipartition (X, Y ) et M ∗
un couplage maximum dans ce graphe. Soit U les noeuds qui ne sont pas
incidents à M ∗ dans X. Soit Z l’ensemble des noeuds atteints par tous les
chemins M ∗ -alternés partant de U . Soient encore
— S =Z ∩X
— T =Z ∩Y
Ces chemins M ∗ -alternés quittent toujours T vers S par une arête de M ∗ ,
et quittent toujours S vers T par une arête hors M ∗ . On remarque (comme
dans la preuve du théorème de Hall) que
— Voisin(S) = T (par construction) ;

41
 — M ∗ est incident à tout T , sinon on aurait un chemin M ∗ -augmenté —
car un chemin alterné qui part de U et qui arrive finalement à y ∈ T
(via une arête hors M ) peut toujours poursuivre par une arête de M ∗ ,
si M ∗ est bien incident à M ∗ , mais doit s’arrêter à y et constituer un
chemin M ∗ -augmenté si M ∗ n’est pas incident à y ;
— M ∗ est incident à tout S\U par construction ;
— M ∗ crée une bijection entre S\U et T — car fM ∗ (S \ U ) ⊆ T et
fM ∗ (T ) ⊆ S \ {u}, où l’on se rappelle que fM ∗ est injective.

On choisit K ∗ = T ∪ (X \ S) et on va montrer que K ∗ est une couverture

de sommets de même taille que |M ∗ |. On aura alors terminé car ceci suffit
à montrer que K ∗ est une couverture minimum.
K ∗ est une couverture de sommets, autrement dit toutes les arêtes ont
une extrémité dans K ∗ car si ce n’est pas le cas, on a une arête du graphe
liant (Y \ T ) à S, or Voisin(S) = T (contradictoire). On va montrer que K
est une couverture minimale et qu’elle vérifie |K ∗ | = |M ∗ |.
Vérifions la taille de cette couverture : |K ∗ | = |X\S| + |T |. Mais T est
en bijection avec S\U . Donc |K ∗ | = |X\S| + |S\U | = |X\U |. Par définition
X\U sont les noeuds de X atteints par M ∗ donc |X\U | = |M ∗ |.

Notons que dans la preuve on n’a pas seulement montré qu’il existe une
couverture minimum K ∗ telle que |K ∗ | = |M ∗ |, on a aussi vu comment on
pouvait la construire connaissant M ∗ .

Exemple 5.16 (Problème du site de rencontres). Soit 5 filles (représen-

tées par les noeuds A, B, C, D, E) et 5 garçons (représentés par les noeuds
a, b, c, d, e) dont les préférences sont représentées dans le graphe biparti ci-
dessous : une arête entre un garçon et une fille indique que ceux-ci s’appré-
cient. On souhaite former un maximum de couples en respectant les préfé-
rences de chacun. Pour cela, il suffit de trouver un couplage maximum dans
ce graphe.

42
 A B C D E

a b c d e

Un couplage possible M est indiqué par les arêtes rouges tandis qu’une
couverture possible des sommets K est réprésentée par les sommets rouges.
Dans ce cas, on voit que |M | = |K|, ce qui garantit que le couplage est
maximum (et donc que la couverture est minimum).

5.3 L’algorithme hongrois

Rassemblant les observations précédentes, on peut concevoir un algo-
rithme qui trouve un couplage maximum dans un graphe biparti défini par
la bipartition (X, Y ). L’algorithme fonctionne en trouvant des chemins M -
augmentés pour augmenter itérativement le nombre d’arêtes du couplage
d’une unité.
Algorithme 5.17 (Algorithme Hongrois).
0. Initialisation. Partir d’un couplage initial arbitraire M . Par exemple
on peut construire M en sélectionnant une première arête arbitraire,
une deuxième qui n’est pas adjacente à la première, une troisème qui
n’est adjacente à aucune des deux premières etc. jusqu’à ce qu’on ne
puisse plus ajouter d’arêtes : on obtient ainsi un couplage M maximal
au sens de l’inclusion.
1. Soit U = {u ∈ X et u non-incident à M }. Si U est vide, le couplage
est maximum (arrêt).
2. A partir d’un sommet u de U , trouver un chemin M -augmenté C.
(a) Si un tel chemin n’existe pas, par le Théorème de Berge, le cou-
plage M est maximum (arrêt).
(b) Sinon, mettre à jour le couplage M comme suit :

M ← (M \ C) ∪ (C \ M )

3. Retour à l’étape 1.
Notons que l’étape 2(b) consiste à inverser les arêtes qui font partie du
couplage le long du chemin M -augmenté C qui a été trouvé.

Exemple 5.18 (Illustration de l’algorithme Hongrois).

43
 1. Couplage initial :

2. Recherche des chemins alternés :

3. nouveau couplage (maximum) :

L’algorithme hongrois (Kuhn-Munkres 1955-1957, se basant sur les tra-

vaux de deux Hongrois, König et Egerváry) se généralise en fait (non-trivialement)
au problème pondéré : étant donné des poids sur les arêtes, comment trouver
le couplage de poids maximum. Dans sa présente version, il est de complexité
O(|V ||E|) (pour un graphe biparti de |V | noeuds et |E| arêtes). L’algorithme
de Hopcroft-Karp (1973) procède de même, avec une stratégie plus intelli-
gente
p pour trouver les chemins augmentés, et une complexité résultante de
O( |V ||E|).
Dans le cadre des graphes non-pondérés généraux (non-bipartis), l’algo-
rithme d’Edmonds (1965) pour trouver le couplage maximum consiste éga-
lement à trouver des chemins augmentés, où la difficulté est de les trouver
2
efficacement, en l’occurrence avec une complexité p de O(|V | |E|). Des tra-
vaux ultérieurs ramènent cette complexité à O( |V ||E|) (Micali-Vazirani
1980).

44
6 Coloriages d’arêtes
Problème des horaires Chaque professeur doit enseigner à un certain
nombre de classes pendant un certain nombre d’heures. On veut créer un
horaire sur le plus petit nombre de périodes possibles.
On relie chaque professeur aux classes auxquelles il donne cours en
veillant a colorier les arêtes en fonction des tranches horaires. Deux arêtes
de même couleur ne peuvent pas être incidentes au même nœud.

Définition 6.1. Un coloriage des arêtes d’un graphe en k couleurs est l’as-
signation à chaque arête d’une couleur 1, 2, . . . , ou k. Ce coloriage est dit
propre si deux arêtes adjacentes sont toujours de couleurs différentes.

Définition 6.2. L’indice chromatique d’un graphe G, noté χ0 (G) est le

nombre minimal de couleurs nécessaire pour obtenir un coloriage propre des
arêtes de G.

Théorème 6.3 (König). Pour tout graphe biparti : χ0 = degmax

Démonstration. On va utiliser le corollaire 5.10 du théorème 5.8 de Hall

pour les graphes bipartis réguliers (qui ont toujours un couplage parfait).
1. Soit un graphe biparti k-régulier, pour k > 0. Par le théorème de Hall,
il existe un couplage parfait. On le colorie en couleur c1 . On consi-
dère ensuite les arêtes restantes non encore coloriées : elles forment
un graphe (k − 1)-régulier. On recommence pour la couleur c2 avec
un autre couplage. On continue jusqu’à épuisement, on obtient alors
χ0 = k.
2. Pour un graphe biparti quelconque de degré maximum k.
— Ajouter des nœuds d’un côté si nécessaire pour avoir le même
nombre de nœuds de chaque côté.
— Si tous les nœuds ne sont pas de degré k, alors il y a au moins un
nœud de degré < k de chaque côté. (En effet pour une bipartition
(X, Y ), la somme des degrés des nœuds de X est la somme des
degrés des nœuds de Y qui est le nombre d’arêtes ; donc, dans la
mesure où |X| = |Y | par construction, si chaque nœud de X a
degré k alors il en est de même pour Y .) On ajoute alors une arête
entre ces deux nœuds de degrés < k. On recommence jusqu’à la
k-régularité.
Par le point 1. , il existe un coloriage propre à k couleurs. On supprime
ensuite les arêtes et nœuds ajoutés : on obtient un coloriage propre
pour le graphe de départ.

⇒ degmax ≤ χ0 ≤ k = degmax

⇒ χ0 = k

45
Théorème 6.4 (Vizing). Pour tout graphe simple : χ0 = degmax ou χ0 =
degmax +1

Démonstration. On sait que χ0 ≥ degmax , il faut donc prouver que χ0 ≤

degmax +1. On présente ici les idées principales de la preuve.
On le prouve par induction sur le nombre d’arêtes du graphe.
Pas inductif : Vrai pour m arêtes. Soit un graphe à m + 1 arêtes, de
degré max k. Je retire une de ces arêtes : il existe un coloriage propre à
≤ k + 1 couleurs.
— Si ce coloriage comporte ≤ k couleurs : je choisis (k + 1) couleurs
pour la (m + 1)ième arête.
— Si k + 1 couleurs c1 , ..., ck+1 : je rétablis la (m + 1)ième arête : il faut
trouver une couleur pour cette arête.
Observation clef : En chaque nœud il y a au moins une couleur libre
(c’est à dire pas utilisée par les arêtes incidentes).
Voici 3 exemples avec k = 3 et 4 couleurs noir, bleu, rouge et vert qui
montrent comment exploiter cette information pour colorier la (m + 1)ième
arête xy.
1. Même couleur libre rouge pour x et pour y donc on peut utiliser le
rouge pour xy.

x x

y y

(e) (f)

2. Pas de couleur libre commune à x et y. Mais le noir est libre pour y,

donc on utilise le noir pour xy, et on efface l’arête noire xy 0 . On se
retrouve alors dans le cas 1. mais pour l’arête xy 0 , que l’on colorie en
vert, couleur libre pour x et pour y 0 .

46
 y y

y0 y0
x x

(g) (h)

3. Quelquefois cette astuce ne suffit pas :

y0
x

y 00

Poour se ramener au cas 1. ou 2., on va libérer une couleur pour

x, disons le noir. Pour ce faire échangeons le noir et rouge le long
du chemin noir-rouge qui prolonge xy 0 . Le coloriage reste propre. Ce
chemin peut impliquer au plus un autre voisin de x, ici y 00 .

y0
x

y 00

A présent le noir, qui était déjà libre pour y, l’est aussi pour x et on
se retrouve dans le cas 1. : on colorie xy en noir.
Pour compléter la preuve, il faudrait montrer que toutes les situations se
résolvent par l’application éventuellement répétée des trois techniques illus-
trées ici. On l’admet sans démonstration.

47
7 Cliques, ensembles indépendants et l’impossible
désordre
7.1 Ensembles indépendants
Théorème 7.1 (Théorème de l’amitié 1). Parmi six personnes, on en trouve
toujours trois qui se connaissent l’une l’autre, ou trois qui sont étrangères
l’une à l’autre.

Démonstration. Considérons le graphe complet K6 pour représenter le pro-

blème. Les nœuds symbolisent les personnes et les arêtes symbolisent les
relations entre elles. Deux personnes sont reliées par une arêtes bleue si elles
se connaissent, et par une arête rouge sinon. On veut montrer que le graphe
contient un triangle bleu ou un triangle rouge.
Chaque nœud x a cinq voisins. On peut donc définir une couleur ma-
joritaire en chaque nœud comme la couleur du plus grand nombre d’arêtes
incidentes. Prenons le cas où la couleur majoritaire pour x est le bleu. Il
existe donc au moins trois arêtes bleues incidentes à x.
x

c
a
b

Considérons trois nœuds a, b et c reliés à x par une arête bleue. Si ces

trois nœuds forment un triangle rouge, alors le graphe contient un triangle
rouge. Sinon, le triangle abc contient au moins une arête bleue. Prenons par
exemple l’arête ab bleue. Le triangle abx est alors bleu. Le graphe contient
donc dans ce cas-ci un triangle bleu.
La preuve reste évidemment valable si l’on prend l’arête bc ou l’arête ac
bleue, de même que si l’on prend le rouge comme couleur majoritaire du
nœud x.

Théorème 7.2 (Théorème de l’amitié 2). En coloriant, de façon arbitraire,

les arêtes du graphe complet à six nœuds en bleu et rouge, on crée un triangle
bleu ou un triangle rouge.

Démonstration. Voir théorème 7.1.

Définition 7.3. Un ensemble indépendant d’un graphe est un ensemble de

nœuds deux à deux non adjacents.

Définition 7.4. Un ensemble indépendant maximum est un ensemble indé-

pendant dont le nombre de nœuds est maximal.

48
Théorème 7.5. Un ensemble de nœuds est indépendant si et seulement si
son complémentaire est une couverture de sommets.

Démonstration. Soit S un ensemble de nœuds indépendant.

S est un ensemble de nœuds indépendant.
⇔ Il n’existe pas d’arête rejoignant 2 nœuds de S.
⇔ Toute arête a au moins une extrémité qui n’est pas incluse dans S.
⇔ Le complémentaire de S est une couverture de sommets.

Exemple 7.6. Complémentaire d’un ensemble indépendant

Couverture de sommets (minimale)

Ensemble indépendant (maximal)

Corollaire 7.7. |ensemble indépendant maximum| + |couverture minimum|

= |nombre de nœuds|

Ainsi, trouver un ensemble indépendant maximum est tout aussi difficile

que de trouver une couverture de sommets minimale.

7.2 Cliques
Définition 7.8. Une clique d’un graphe est un ensemble de nœuds deux à
deux adjacents. Autrement dit, c’est un sous-graphe complet.

Définition 7.9. Une clique maximum est une clique dont le nombre de
nœuds est maximal.

Théorème 7.10. Un ensemble est indépendant dans un graphe simple si

et seulement s’il est une clique dans le graphe complémentaire.

Démonstration. Soit S un ensemble indépendant dans un graphe simple G.

S est un ensemble indépendant de G
⇔ Deux nœuds quelconques de S sont non-adjacents dans G.
⇔ Deux nœuds quelconques de S sont adjacents dans le complémentaire
de G.
⇔ S est une clique dans le complémentaire de G.

49
Exemple 7.11. Voici le complémentaire du graphe de l’exemple 7.6. Les
sommets de l’ensemble indépendant de ce dernier exemple sont devenus les
sommets d’une clique (en rouge) dans le graphe complémentaire. L’ensemble
indépendant étant maximum, la clique l’est également.

On peut ainsi reformuler le théorème de l’amitié de cette façon :

Théorème 7.12 (Théorème de l’amitié 3). Tout graphe simple à six nœuds
contient une clique de trois nœuds ou un ensemble indépendant de trois
nœuds.
Définition 7.13 (Nombres de Ramsey). Le nombre de Ramsey R(n1 , . . . , nk )
est le plus petit naturel r tel que tout coloriage du graphe complet de r
nœuds en k couleurs c1 , . . . , ck crée une clique de n1 nœuds de couleur c1 ,
ou une clique de n2 nœuds de couleur c2 , ..., ou une clique de nk nœuds de
couleur ck .
Théorème 7.14 (Théorème de Ramsey). Le nombre de Ramsey R(n1 , . . . , nk )
existe.
On le prouve d’abord pour k = 2 couleurs.
Théorème 7.15 (Théorème d’ Erdös et Szekeres). Pour m, n ≥ 2 : R(m, n) ≤
R(m, n − 1) + R(m − 1, n).

Démonstration. Prenons un noeud quelconque u dans un graphe complet à

R(m, n − 1) + R(m − 1, n) noeuds avec des arêtes coloriées en bleu (couleur
1) ou en rouge (couleur 2). On doit démontrer qu’il y a soit une m-clique
monochrome bleue, soit une n-clique monochrome rouge.
Soit M et N définis tels que

M = {voisins de u reliés par des arêtes bleues}

N = {voisins de u reliés par des arêtes rouges}.

On obtient en comptant les nœuds :

|M | + |N | + 1 = R(m, n − 1) + R(m − 1, n).

Donc on a que
|M | ≥ R(m − 1, n) (3)
ou bien
|N | ≥ R(m, n − 1) (4)

50
 M

Si on est dans le cas de figure de l’inégalité 3, il y a deux possibilités. Soit

il existe une clique rouge de n nœuds dans M ce qui implique qu’il existe
une clique rouge de n nœuds dans le graphe. Soit il existe une clique bleue
de m − 1 nœuds dans M ce qui en incluant u fait une clique bleue de m
nœuds dans le graphe.
Si on est dans le cas de figure de l’inégalité 4, idem mutatis mutandis.

Ceci démontre bien sûr que R(m, n) existe pour tout m, n, par induc-
tion sur m et n. On peut même vérifier que l’(in)équation de récurrence
se solutionne
de la façon suivante, en se souvenant de
l’identité du triangle
p!
de Pascal pq = p−1 p−1

se souvient que pq = q!(p−q)!


q−1 + q . On dénote le
nombre d’ensembles de q éléments pris parmi p éléments.
m+n−2

Corollaire 7.16. Pour tout m, n ≥ 1 on a R(m, n) ≤ m−1 .

Démonstration. On le démontre par induction sur (m, n).

Ici l’induction n’est pas sur un entier naturel comme c’est souvent le cas,
mais un couple d’entiers naturels ; il est donc peut-être utile de rappeler ou
résumer le cadre général des preuves par induction. Quand on veut montrer
par induction qu’une propriété P (x) est vraie pour pour tout x ∈ X, on
munit l’ensemble X d’un ordre ≤, c-à-d une relation réflexive (x ≤ x),
transitive (x ≤ y et y ≤ z impliquent x ≤ z) et anti-symétrique (x ≤ y
et y ≤ x impliquent x = y). L’ordre strict x < y est défini bien sûr par
x ≤ y et x 6= y. On exige que l’ordre est bien fondé, c-à-d ne possède pas
de suite infinie strictement décroissante. Par exemple l’ordre habituel sur
les entiers naturels est bien fondé, mais par l’ordre habituel sur les réels ou
les entiers (positifs ou négatifs). Si on démontre que l’hypothèse d’induction
∀y < x : P (y) implique P (x), alors on peut conclure que ∀x : P (x) : c’est le
principe d’induction (admis sans démonstration dans ce cours). Notons que
ceci implique en particulier de démontrer le cas de base pour les éléments
minimaux de l’ordre : si on n’a pas de y tel que y < x alors l’hypothèse
d’induction est automatiquement vérifiée et il faut montrer que P (x).
Dans cette preuve on choisit l’ordre (m, n) ≤ (m0 , n0 ) ssi m ≤ m0 et
n ≤ n0 . Ce n’est pas le seul ordre possible sur N2+ mais il est clairement bien
fondé et convient à notre preuve.

51
 Le cas de base ici est m = 1 ou n = 1 : on vérifie que R(1, n) = 1 = n−1


0
et R(m, 1) = 1 =≤ m−1


m−1 , ce qui satisfait l’inégalité.
Ensuite le pas inductif pour m, n ≥ 2 : on suppose en particulier que les
inégalités suivantes sont déjà démontrées :
!
m+n−3
R(m − 1, n) ≤
m−2

et !
m+n−3
R(m, n − 1) ≤
m−1
En les additionnant et en appliquant le théorème 7.15 sur les membres de
gauche, ainsi que l’identité du triangle de Pascal sur les membres de droite,
on obtient le résultat attendu.

Le théorème suivant fournit l’argument inductif aboutissant au théorème

de Ramsey pour un nombre arbitraire de couleurs.

Théorème 7.17. R(n1 , ..., nk ) ≤ R (n1 , ..., nk−2 , R(nk−1 , nk )).

Démonstration. Prenons un graphe complet à R(n1 , ..., nk−2 , R(nk−1 , nk ))

nœuds et leurs arêtes coloriées en k couleurs c1 , c2 , . . . , ck .
Faisons momentanément semblant que ck−1 et ck sont une seule couleur.
Cela implique qu’il n’y a plus que k − 1 couleurs. Il existe donc une clique à
n1 nœuds de couleur c1 ou bien une clique à n2 nœuds de couleur c2 et ainsi
de suite jusqu’à la possibilité d’une clique de R(nk−1 , nk ) nœuds de couleur
ck−1 ou ck .
Or par définition de R(nk−1 , nk ), cette dernière possibilité revient à dire
qu’il existe une clique de nk−1 nœuds de couleur ck−1 ou une clique de nk
nœuds de couleur ck .

Ceci prouve bien le théorème de Ramsey, par récurrence sur le nombre

k de couleurs, avec le théorème d’Erdös-Szekeres comme cas de base.

Théorème 7.18 (Théorème de l’amitié 4). R(3, 3) = 6

Démonstration. Cela découle directement du théorème 7.2.

Quoique les nombres de Ramsey soient difficiles à calculer, on peut pro-

duire des bornes supérieures, comme ci-dessus, et des bornes inférieures,
telles que ce théorème d’Erdös :
m(m−1)
N
−1
Théorème 7.19 (Erdös). Si N est tel que m <2 2 alors R(m, m) >
N

52
Démonstration. Il s’agit de montrer que pour un tel N il existe un coloriage
en deux couleurs (disons bleu et rouge) des arêtes de KN qui ne comporte
aucune m-clique monochrome.
Pour le montrer on utilise la méthode probabiliste. On génère un coloriage
aléatoire en choisissant la couleur bleue ou rouge pour chaque arête avec
probabilité 1/2 indépendamment des autres arêtes. Il suffit de démontrer
la probabilité de n’avoir aucune m-clique monochrome est non-nulle pour
démontrer l’existence d’un tel coloriage.
Alternativement on démontre que la probabilité d’avoir une m-clique
monochrome est < 1 :

X
Proba[∃ m-clique monochrome] ≤ Proba[arêtes entre {v1 , . . . , vm } monochromes]
noeuds{v1 ,...,vm }
X 1 m(m−1)
= 2( ) 2
noeuds{v1 ,...,vm }
2
!
N − m(m−1) +1
= 2 2
m
<1

Ce théorème est important notamment pour sa méthode de preuve, qui

est devenu depuis un outil important en combinatoire.

Le théorème de Ramsey ne nous dit pas de quelle couleur est la clique

monochrome, lacune partiellement comblée par le théorème suivant.
Théorème 7.20 (Théorème de Turán). Si un graphe simple possède stric-
2
tement plus de (1 − 1r ) n2 arêtes, alors il a une clique de r + 1 nœuds.

7.3 La théorie de Ramsey

Beaucoup de théorèmes existent qui imitent le théorème de Ramsey et
prouvent quelque chose du genre, en termes informels :
— “Dans un machin suffisamment grand, il y a toujours des sous-machins
avec une certaine propriété.”
— “Dans un grand machin, même tout-à-fait quelconque, un certain
ordre est inévitable.”
— “Le désordre complet est impossible.”
Voyons quelques exemples.
Théorème 7.21 (Sommes d’entiers). Si l’on colorie les nombres de un à
quatorze en trois couleurs alors il existe trois nombres (pas forcément dis-
tincts) x, y et z de même couleur tels que x + y = z.

53
Exemple 7.22. Séparons les nombres de 1 à 13 en trois couleurs :

couleur1 1 4 10 13
couleur2 2 3 11 12
couleur3 5 6 7 8 9

On vérifie que quelle que soit la couleur attribuée au 14, la propriété sera
vérifiée.

Théorème 7.23 (Théorème de Schur). Pour chaque k, il y a un nombre rk

tel que pour toute partition des nombres 1, 2, ...., rk en k classes, une de ces
classes contient x, y (possiblement égaux) et z tels que x + y = z. 4

Démonstration. Nous montrons que l’on peut choisir rk = R(3, ..., 3).
| {z }
k
Colorions les arêtes du graphe à rk nœuds, sachant qu’on a réparti arbi-
trairement ses nœuds dans les classes S1 , S2 , ...., Sk .
Nous allons les colorier de la manière suivante : l’arête ij est dans la
couleur c ssi | i − j |∈ Sc . Nous utilisons donc k couleurs différentes pour les
arêtes.
Par le théorème de Ramsey, il y a un triangle monochrome. Donc il y a
i, j et l tels que :
— i<j<l
— j − i, l − j, l − i sont dans la même classe.
On prend alors x = j − i, y = l − j et z = l − i, d’où x + y = z.

Théorème 7.24 (Théorème d’Esther Klein). Parmi cinq points arbitraires

dans le plan, tels que trois d’entre eux ne sont jamais alignés, on peut tou-
jours en choisir quatre qui déterminent un quadrilatère convexe.

Théorème 7.25. Si l’on colorie les nombres de un à neuf en deux cou-

leurs. Alors il existe une progression arithmétique de longueur trois qui est
monochrome.

Théorème 7.26 (Théorème de Van der Waerden). Pour tout k, `, il existe

un nombre W (k, `) tel que les nombres de 1 à W (k, `), coloriés arbitrairement
en k couleurs, contiennent une progression arithmétique monochrome de
longueur `.

Exemple 7.27. Cherchons W (2, 3) expérimentalement.

12345678
On ne sait comment colorier le huit car si on le met en rouge on crée la
suite arithmétique 6, 7, 8, de raison un et en vert la suite 2, 5, 8, de raison
3.
4. dans l’exemple ci-dessus k = 3 et rk = 14

54
 Parmi les théorèmes les plus avancés de la théorie de Ramsay, on trouve
celui-ci :

Théorème 7.28 (Théorème de Green-Tao, 2004). La suite des nombres

premiers contient des sous-suites en progression arithmétique arbitrairement
longues.

Par exemple 5, 11, 17, 23, 29 est suite de raison 6 et de longueur 5,

composée uniquement de nombres premiers.

55
8 Coloriages de sommets
8.1 Coloriages de sommets et nombre chromatique
Définition 8.1. Un coloriage ou une coloration des noeuds (parfois appellé
également sommets-coloration) est l’attribution à chaque noeud d’une cou-
leur. Le coloriage est dit propre si des noeuds adjacents ont des couleurs
différentes (on parlera toujours implicitement de coloriages propres). On
parle de k-coloriage du graphe quand on se restreint à k couleurs au plus.

Définition 8.2. Un coloriage minimum est un coloriage propre qui em-

ploie un nombre minimal de couleurs. Le nombre chromatique, noté χ(G),
d’un graphe G est le nombre minimal de couleurs d’un coloriage propre de
sommets du graphe :

χ(G) = min{k ∈ N | ∃ k-coloration de G}.

Exemple 8.3. Un graphe est biparti ssi son nombre chromatique est χ ≤ 2
(il suffit de colorier les noeuds selon leur classe de la bipartition du graphe,
le cas χ = 1 est pour des noeuds isolés). Le graphe complet à n noeuds
Kn (chaque noeud est adjacent à tous les autres) a χ(Kn ) = n. Un graphe
constitué d’un simple cycle ont un nombre chromatique égal à 2 (3) si le
nombre de noeuds est pair (impair). Un graphe dit “planaire” a χ ≤ 4, voir
chapitre sur les graphes planaires.

8.2 Bornes sur le nombre chromatique

Théorème 8.4. |clique max| ≤ χ

Démonstration. Dans une clique, chaque noeud est adjacent à tous les autres,
donc tous les noeuds de la clique doivent avoir une couleur différente. Il
faut donc au minimum une couleur différente pour chaque noeud de la plus
grande clique du graphe.

Théorème 8.5. χ ≤ degmax +1

Démonstration. On explique d’abord le coloriage glouton, qui fonctionne de

la façon suivante. On ordonne toutes les couleurs, que l’on nomme 1, 2, 3, . . ..
On visite les noeuds du graphe dans un ordre arbitraire v1 , . . . , vn . A chaque
noeud vi visité, on choisit la plus petite couleur disponible, différente des cou-
leurs déjà attribuées au voisins de vi parmi les noeuds déjà visités v1 , . . . , vi−1 .
A la fin, on regarde le nombre de couleurs utilisés, qui est aussi le numéro
de la plus grande couleur utilisée.
Puisque les voisins de vi sont au nombre de degmax ou moins, il y a
toujours une couleur disponible de numéro ≤ degmax +1 pour colorier vi .

56
 Cette borne n’est pas améliorable dans l’absolu, puisqu’elle atteinte pour
un cycle impair ( degmax = 2, χ = 3) et pour un graphe complet Kn (
degmax = n − 1, χ = n). Toutefois, dans cette preuve on constate que l’on
visite les noeuds dans n’importe quel ordre. Cela fait beaucoup de liberté !
On se dit qu’on choisissant un ordre de façon intelligente pour le coloriage
glouton, on peut peut-être réduire le nombre de couleurs utilisées, du moins
pour certains graphes.

Théorème 8.6 (Brooks). Pour tout graphe connexe G de degré maximal

degmax , χ ≤ degmax sauf si G est un graphe complet ou un cycle de longueur
impaire (auxquels cas χ = degmax +1).

On prouve le Théorème de Brooks par étapes.

Lemme 8.7. Dans un graphe connexe non-régulier, χ ≤ degmax .

Démonstration. Le graphe étant non-régulier il existe un noeud u de degré

strictement inférieur à degmax .
A partir de u je crée un arbre sous-tendant de racine u (par exemple via
un parcours en profondeur à partir de u).
Je colorie l’arbre de façon gloutonne en commençant par les feuilles de
façon à ce que chaque noeud soit colorié avant son parent (et avec u colorié
en dernier). Par exemple lors d’un parcours en profondeur, je colorie chaque
noeud la dernière fois que je le visite, au moment où je l’enlève de la pile de
noeuds encore à explorer.

Pour tout noeud différent de u il y a au plus degmax −1 voisins déjà colo-

riés (puisque le parent n’est pas encore colorié), donc une couleur ≤ degmax
suffit pour le colorier. Le noeud u est sans parent, mais il a strictement moins
de degmax voisins par hypothèse, et donc il reste une couleur ≤ degmax de
libre. Au total on a eu besoin de degmax couleurs au plus.

Lemme 8.8. Si un graphe G est connexe et régulier de degré k mais pas

2-connexe alors χ ≤ k.

57
Démonstration. Il n’est pas 2-connexe, il existe donc un noeud u tel que
G − u est non-connexe. Séparons le graphe en deux sous-graphes, G1 et G2 ,
uniquement liés via u et tel que G = G1 ∪ G2 et G1 ∩ G2 = {u}.

G1 G2

Le degré de u dans G1 est strictement inférieur à k et le Lemme précédent

s’applique. Donc k couleurs ou moins sont suffisantes.
Le même raisonnement s’applique pour G2 . Éventuellement on échange
2 couleurs du coloriage de G2 pour qu’il soit consistant avec le coloriage de
G1 sur le noeud u.

On traite les cas de graphes connexes réguliers pour k = 0, 1, 2.

— k = 0 : un noeud isolé, χ = 1.
— k = 1 : deux noeuds liés, χ = 2.
— k = 2 : soit un cycle de longueur paire, χ = 2 ; soit de longueur
impaire, χ = 3.

Lemme 8.9. Si un graphe G est connexe, k-régulier pour k ≥ 3, et tel qu’il

existe une coupe de 2 noeuds non-adjacents alors χ ≤ k.

Démonstration. Même idée générale que le Lemme précédent, détails admis.

Preuve du Théorème de Brooks. On sépare la preuve en différents cas.

Non régulier. Lemme 8.7.
k-régulier avec k < 3. Les trois cas ont été traités.
k-régulier avec k ≥ 3 et il n’existe pas deux noeuds non-adjacents. Le graphe
est alors complet.
k-régulier avec k ≥ 3 et il existe deux noeuds non-adjacents. Il existe un
noeud u tel qu’il existe deux voisins de u non-adjacent entre eux, v
et w.
Si le graphe G − v − w est non-connexe ces deux noeuds forment une
coupe et le Lemme 8.9 s’applique.
On peut donc continuer en supposant que G − v − w est connexe.
J’applique le coloriage glouton, avec un ordre des noeuds bien choisi :
je construis un arbre sous-tendant de G − v − w partant de u puis
j’y ajoute v et w comme feuilles directement reliées à u. Je colorie
en commençant par les feuilles v et w en leur donnant la couleur 1

58
 (ils sont non-adjacents), puis je continue le coloriage en partant des
autres feuilles de l’arbre et en remontant vers u, de sorte que chaque
noeud (n equ) soit colorié avant son parent.
Tout les noeuds différents de u peuvent être coloriés avec une couleur
≤ k en appliquant cette stratégie. Les noeuds v et w ayant la même
couleur, u a au plus k − 1 couleurs dans ses voisins et donc une k ième
est disponible.

Malgré ces bornes, trouver le nombre chromatique d’un graphe général

est un problème difficile (il n’existe pas d’algorithme efficace).

8.3 Polynôme chromatique

Pour un graphe G, le nombre de coloriage propres différents à k couleurs
est noté πG (k). On peut donc écrire χ(G) = min{k ∈ N | πG (k) > 0}.
Par exemple, πG (k) = k n pour n noeuds isolés, et πG (k) = k(k −
1) . . . (k − n + 1) pour G = Kn . Pour un arbre à n noeuds, on a πG (k) =
k(k − 1)n−1 . Pour des graphes généraux cependant, il est plus difficile de
trouver une expression explicite de πG (k). Le théorème suivant peut parfois
nous aider.

Théorème 8.10. Pour toute arête e du graphe G,

πG (k) = πG−e (k) − πG.e (k),

où G.e est le graphe obtenu en contractant l’arête e (fusionnant les deux

noeuds incidents à e, et éliminant les boucles éventuellement obtenues sur
le noeud résultant).

Démonstration. Soit u et v les deux extrémités de e.

— πG−e (k) est le nombre de coloriages des noeuds de G à moins de k
couleurs qui sont propres sauf possiblement entre u et v. On peut
avoir u et v de même couleur ou de couleur différente.
— πG.e (k) est le nombre de coloriages des noeuds de G à moins de k
couleurs qui sont propres sauf entre u et v. On doit avoir u et v de
même couleur.
On a donc finalement πG−e (k) − πG.e (k) est le nombre de coloriages des
noeuds de G à k couleurs ou moins qui sont propres même entre u et v : on
doit avoir u et v de couleurs différentes.

Notons que G.e contient éventuellement des arêtes multiples, même si

G est simple. On peut alors les fusionner en une arête simple, c’est sans
importance pour les questions de coloriage de noeuds.

59
Corollaire 8.11 (Birkhoff). Pour un graphe G à n noeuds, πG (k) est un
polynôme monique de degré n, de terme constant nul et dont les coefficients
alternent en signe.

Démonstration. Par récurrence sur le nombre d’arêtes et en utilisant πG (k) =

πG−e (k) − πG.e (k). Le cas de base correspond aux noeuds isolés, il y a exac-
tement k n coloriages possibles. Le pas inductif s’obtient en constatant que
G − e et G.e ont strictement moins d’arêtes que G, et le même nombre de
noeuds (pour G − e) ou un noeud de moins (pour G.e).

60
9 Graphes planaires
Un graphe est planaire si il possède une représentation dans le plan dont
les arêtes ne se touchent pas, sauf à leurs extrémités.

Théorème 9.1 (Conjoncture des quatre couleurs). Quatre couleurs suffisent

toujours pour colorier une carte

Démonstration. On suppose qu’en chaque point se rencontrent au maximum

trois pays, et que les pays sont d’un seul tenant.

61
 Il est possible de partir du graphe correspondant en remplacant les pays
par des sommets et les frontières par des arêtes. Ce graphe est alors planaire.
Il suffit alors de montrer que tout graphe planaire a un nombre chromatique
χ ≤ 4 (ou de manière équivalente, admet au moins un coloriage de quatre
couleurs).

Notons qu’un graphe planaire peut être dessiné de manière non planaire.
•

• •

• •

• •
•

• •

• •

• •

9.1 Graphes planaires

Théorème 9.2 (Fáry). Tout graphe planaire simple peut être représenté
en n’utilisant que des arêtes droites.

Théorème 9.3. Le graphe complet K5 à cinq noeuds n’est pas planaire.

62
Démonstration. Représentons K5 dans le plan. Soit l’ensemble de ses noeuds
{v1 , v2 , v3 , v4 , v5 }.
v1 , v2 et v3 forment un triangle. Où placer v4 ?

v3

v1 v2

1. A l’intérieur du triangle formé par v1 , v2 et v3 ?

v3

v4

v1 v2

Où placer v5 ?
(a) A l’intérieur du triangle formé par v1 , v3 et v4 ? Le graphe ne se-
rait plus planaire puisqu’il faudrait couper le triangle v1 , v3 et v4
pour relier v5 à v2 .

63
 v3

v5
v4

v1 v2

(b) A l’intérieur de v1 , v2 , v4 ou de v2 , v3 , v4 ? Idem.

(c) A l’extérieur de v1 , v2 , v3 ?

v3

v5

v4

v1 v2

2. A l’extérieur de v1 , v2 , v3 ? En applicant le même type d’énumération

qu’au point précédent, on trouve qu’il n’y a aucune manière de repré-
senter K5 dans le plan de manière à ce qu’il soit planaire.

Théorème 9.4. Le graphe complet biparti K3,3 à 3 + 3 noeuds n’est pas

planaire.

Définition 9.5. Une subdivision d’un graphe est un graphe obtenu en rem-
plaçant une ou plusieurs arêtes par un chemin (de longueur 1 ou plus).

Théorème 9.6 (Kuratowski). Un graphe est non planaire si et seulement

s’il contient comme sous-graphe K5 ou K3,3 ou une subdivision de ceux-ci.

Théorème 9.7. Une subdivision d’un graphe non planaire est non-planaire,
et un sous-graphe d’un graphe planaire est planaire.

64
Définition 9.8. Un graphe planaire (dans une représentation sans croise-
ment) découpe le plan en plusieurs régions connexes (au sens géométrique).
Ces régions sont appelées faces. Il y a une et une seule face non bornée,
nommée face extérieure, les autres faces sont intérieures.

Définition 9.9. On identifie le bord d’une face au parcours fermé qui longe
la face. Le bord parcourt chaque arête une ou deux fois. Une face est inci-
dente aux arêtes et sommets qui sont sur son bord. Le degré d’une face est
la longueur du bord, donc le nombre d’arêtes incidentes (comptées une ou
deux fois).

Définition 9.10. Etant donné un graphe planaire G (dans une représenta-

tion sans croisement), construisons G∗ , graphe dont les sommets sont les
faces de G, reliés si et seulement si les faces correspondantes ont dans G une
arête en commun. Ce graphe G∗ est le dual de G (dans cette représentation).

Exemple 9.11. Exemple :

Graphe Dual
4 faces
1 • Face extérieure : 1234521
degré(face extérieure) = 6

5 • 6 • 3

4 Face extérieure

65
Théorème 9.12. La somme des degrés des faces est deux fois le nombre
d’arêtes.

Démonstration. On passe au graphe dual, sur lequel on applique le théorème

des poignées de mains.

Théorème 9.13. Un graphe est planaire si et seulement si il est représen-

table sur la sphère sans croisement d’arêtes.

Démonstration. On utilise la projection stéréographique pour passer d’une

représentation planaire à une représentation sphérique et vice versa.

9.2 Formule d’Euler

Théorème 9.14 (Formule d’Euler). Dans un graphe planaire connexe à n
sommets, e arêtes et f faces :

n−e+f =2

Démonstration. On démontre cette égalité par récurrence sur le nombre de

faces
Initialisation S’il y a une seule face, alors le graphe est sans cycle car
chaque cycle créé au moins 2 faces, la face intérieure au cycle et la face
extérieure au cycle. C’est donc un arbre d’où e = n − 1, c’est à dire
n − e + f = 2 car f = 1.
Induction Soit un graphe G avec f > 1 faces. Comme les arbres ont une
seule face, G possède un cycle et donc deux faces adjacentes. Soit G0
obtenu en supprimant une arête entre les deux faces. Les deux faces
deviennent une seule face pour G0 . Ce graphe a donc f − 1 faces et
e − 1 arêtes, par l’hypothèse de récurrence sur G0 , on a

n − (e − 1) + (f − 1) = 2
=⇒ n − e + f = 2.

Théorème 9.15. Dans tout graphe planaire simple à n ≥ 3 sommets et e

arêtes, e ≤ 3n − 6.

Démonstration. Commençons par montrer que pour toute face f , deg(f ) ≥

3. Pour la face extérieure, c’est vrai car n ≥ 3. Pour une face intérieure,
comme le graphe est simple, la plus petite face en terme de degré est un
triangle donc c’est vrai également.
On a donc X
deg(f ) ≥ 3|F |.
f ∈F

66
Or par le théorème des poignées de main dual,
X
deg(f ) = 2|E|.
f ∈F

Et donc
2
e ≥ |F |. (5)
3
En injectant 5 dans la formule d’Euler, on obtient
2
2 = n − e + |F | ≤ n − e + e
3
d’où
1
e ≤ n − 2.
3

Théorème 9.16. Pour tout graphe planaire simple, il y a un noeud de degré

≤ 5.

Démonstration. On va montrer que le degré moyen est < 6. Ce qu’il voudra

dire qu’il existe un noeud de degré ≤ 5.
P
v∈V deg(v)
degavg =
|V |
2|E|
= .
|V |

Considérons 2 cas
— Si |V | < 3, l’énoncé est trivial car dans un graphe simple, pour tout
v ∈ V , deg(v) ≤ |V | − 1 du coup deg(v) ≤ |V | − 1 < 2 ≤ 5 pour tout
v.
— Comme notre graphe est simple, on peut utiliser le théorème 9.15, on
a donc |E| ≤ 3|V | − 6. Dès lors

3|V | − 6
degavg ≤ 2
|V |
12
=6− < 6.
|V |

Corollaire 9.17. K5 est non planaire.

Démonstration. K5 a 5 noeuds et 10 arêtes. Par le théorème 9.15, |E| ≤

3|V | − 6. Il faut donc que 10 ≤ 3 · 5 − 6 = 9, ce qui est faux. Le graphe est
par conséquent non planaire.

67
Corollaire 9.18. K3,3 est non planaire.

Démonstration. Supposons que K3,3 soit planaire et montrons une contra-

diction.
Le graphe K3,3 a 6 noeuds et 9 arêtes. C’est un graphe biparti donc les
cycles sont de longueurs paires, de plus il est simple donc tous les cycles
ont une longueur ≥ 4. Donc toutes les faces ont un degré ≥ 4. On a
alors f ∈F deg(f ) ≥ 4|F | et par le théorème des poignées de main dual,
P
18
f ∈F deg(f ) = 2|E| = 18. Donc |F | ≤ 4 = 4.5.
P

Par la formule d’Euler, il faut que :

|F | − |E| + |V | = 2

or
|F | − |E| + |V | ≤ 4.5 − 9 + 6 = 1.5.
K3,3 ne peut donc pas être planaire.

9.3 Les cinq solides platoniciens

Définition 9.19. Un solide platonicien est un polyèdre convexe régulier.
C’est-à-dire que toutes les faces, sommets et arêtes sont identiques à une
rotation près.

Théorème 9.20. Il y a 5 solides platoniciens.

Démonstration. Les polyèdres convexes correspondent à des graphes pla-

naires, via projection. Le fait qu’ils soient platoniciens nous dit que chaque
noeud est de même degré p et que chaque face est de même degré q.
La formule d’Euler |F | − |E| + |V | = 2
Poignées de main p|V | = 2|E|
Poignées de main dual q|F | = 2|E|
Donc
2 2
|E| − |E| + |E| = 2
q p
2 2 2
−1+ = >0
q p |E|
1 1 1
+ > .
q p 2

On sait donc que soit p, soit q est < 4 (ou les deux). Or p ≥ 3 et q ≥ 3 (par
géométrie, graphes planaires simple de dual simple : toute face a au moins
trois côtés, tout sommet a au moins trois voisins). Les possibilités sont

68
 p q |V | |F | |E| Polyèdre
3 3 4 4 6 Tétraèdre
3 4 8 6 12 Cube
4 3 6 8 12 Octaèdre
3 5 20 12 30 Dodécaèdre
5 3 12 20 30 Icosaèdre
Il reste a montrer que chacune de ces possibilités pour p et q est réalisée
par un unique polyèdre régulier (indiqué dans la colonne de droite) : c’est
la partie ‘géométrique’ de la preuve, que nous admettons ici.

9.4 Coloriage des graphes planaires

Théorème 9.21 (Kempe). Tout graphe planaire possède un coloriage propre
à cinq couleurs. “Toute carte peut être coloriée avec 5 couleurs”. Nombre
chromatique χ (graphe planaire) ≤ 5.

Démonstration. Par récurrence : “on enlève un noeud, on colorie par hyp.

de récurrence, on remet le noeud.” On peut supposer le graphe G simple
(car arêtes multiples n’affectent pas χ). Il existe un noeud u de degré ≤ 5.
On enlève u, on a encore un graphe planaire, on le colorie. On rétablit u :
— si deg(u) < 5 : facile, on utilise une couleur non utilisée par les voisins
pour u.
— Si deg(u) = 5 : Si ces 5 voisins utilisent < 5 couleurs : facile aussi. Si 5
couleurs utilisées : numérotons les 5 noeuds voisins v1 , v2 , v3 , v4 , v5 , lus
dans l’ordre horloger (ou anti-horloger) autour de u. Soient c1 , c2 , c3 , c4 , c5
leurs couleurs respectives. Regardons v1 et v3 , et le sous-graphe c1 −c3
de tous les noeuds de couleurs c1 ou c3 et leurs arêtes. Si v1 et v3
sont sur des composantes connexes différentes de ce sous-graphe :
on échange c1 et c3 sur la composante connexe (dans le sous-graphe
c1 − c3 ) de v3 dans G \ u, et on colorie u en c1 .Si v1 et v3 sont
dans la même composante connexe (c1 − c3 ) : Maintenant v2 et v4
sont dans des composantes connexes différentes (dans le sous-graphe
des noeuds couleurs c2 − c4 ), sinon la planarité serait violée. Même
raisonnement : échanger c2 et c4 sur composante connexe (v2 ).

69
 (c1 − c3 ) (c2 − c4 )

v1 v2 v3 v4 v5

Théorème 9.22 (Appel, Haken). Tout graphe planaire possède un coloriage

propre à quatre couleurs.

70
10 Flots et coupes
10.1 Flots et coupes
Définition 10.1. Un réseau est un graphe dirigé G = (V, E, ϕ), dont les
noeuds sont partitionnés en sources, puits et noeuds intermédiaires, et dont
chaque arête e porte un nombre réel c(e) nommé capacité. Un flot (d’un
réseau) est une fonction f (e) sur les arêtes, telle que la capacité limitée soit
respectée :
0 ≤ f (e) ≤ c(e) ∀e ∈ E,
et que le flot net sortant de chaque noeud intermédiaire soit nul (équation
de conservation, "ce qui rentre doit sortir") :
X X
f (uv) = f (vu) ∀v étant un noeud intermédiaire.
u∈V u∈V

Définition 10.2.
— Le flot net sortant d’un noeud u est défini comme
X X
fnet (u) = f (a) − f (b).
arêtes a d’origine u arêtes b de destination u

— Le flot net sortant d’un ensemble U de noeuds est la somme des flots
nets sortant des noeuds de U .
— La valeur du flot, notée valeur(f ), est le flot net sortant de l’ensemble
des noeuds sources.

s1 2/4 1/1
1/2
0/2 1/2 0/1 t
2/4
s2 1/1 2/2

Figure 2 – Exemple de flot avec pour chaque arête e, f (e)/c(e). Il y a deux

noeuds sources s1 et s2 ainsi qu’un noeud puits t.

Exemple 10.3. Pour le flot f de la figure 2, on voit que fnet (s1 ) = 2 − 0 = 2

et fnet (s2 ) = 1. On a donc

valeur(f ) = fnet ({s1 , s2 }) = fnet (s1 ) + fnet (s2 ) = 2 + 1 = 3.

On s’intéressera au problème du flot maximum fmax , c’est-à-dire trouver

le flot dont la valeur est maximale. Ce problème est lié à celui de la coupe
minimum.

71
Définition 10.4. Une coupe (d’un réseau) est un ensemble d’arêtes tel qu’il
n’y ait plus aucun chemin d’un noeud source vers un noeud puits quand on
retire cet ensemble du graphe. La capacité d’une coupe est la somme des
capacités des arêtes constituant la coupe.

On s’intéressera au problème de la coupe minimum, c’est-à-dire la coupe

dont la capacité est minimale.

Observation Une coupe minimale peut être décrite par un ensemble S de

noeuds atteignables à partir des sources. Lorsqu’on a une coupe, S est la
composante connexe comprenant les sources lorsqu’on enlève les arêtes de
la coupe. En d’autres mots, la coupe est donc l’ensemble des arêtes reliant
les noeuds de S (tous les noeuds sources doivent appartenir à S) à ceux de
S̄ (tous les noeuds puits doivent appartenir à S̄).

On note alors la coupe S → S̄ et, étant donné un certain flot pour le

réseau, le flot net à travers la coupe est le flot net de l’ensemble S
XX XX
fnet (S → S̄) = fnet (S) = f (uv) − f (vu).
u∈S v∈S̄ v∈S̄ u∈S

Lemme 10.5. Pour un flot donné, toutes les coupes ont le même flot net,
qui est la valeur du flot.

Démonstration. Soit une coupe S → S̄ et s l’ensemble des sources (rappel :

S \ s ne contient que des noeuds intermédiaires qui ont donc un flot net nul
par l’équation de conservation),

fnet (S → S̄) = fnet (S)

= fnet (s) + fnet (S \ s)
= fnet (s)
= valeur(f )

ou la dernière égalité est la définition de la valeur du flot.

Lemme 10.6. Pour tout flot f et toute coupe S → S̄,

valeur(f ) ≤ capacité(S → S̄).

L’égalité a lieu si et seulement si toutes les arêtes a de la coupe S → S̄ sont

f -saturées (i.e., f (a) = c(a)) et toutes les arêtes b de S̄ → S sont f -nulles
(i.e., f (b) = 0).

72
Démonstration. On prend comme point de départ le lemme précédent :

valeur(f ) = fnet (S → S̄)

X X
= f (ij) − f (ji)
i∈S i∈S
j∈S̄ j∈S̄
ij∈E ji∈E
X
≤ f (ij)
i∈S
j∈S̄
ij∈E
X
≤ c(ij)
i∈S
j∈S̄
ij∈E

= capacité(S → S̄).
P P P
Avec égalité si et seulement si i∈S f (ji) = 0 et i∈S f (ij) = i∈S c(ij)
j∈S̄ j∈S̄ j∈S̄
ji∈E ij∈E ij∈E
c’est à dire que toutes les arêtes qui lient un noeud de S à un noeud de S̄
sont saturées et que les arêtes qui lient un noeud de S̄ à un noeud de S ont
un flot nul.

Corollaire 10.7. Si un flot f et une coupe S → S̄ sont tels que

valeur(f ) = capacité(S → S̄),

alors ce flot est maximum et cette coupe minimum.

Démonstration. On sait que pour toute coupe S → S̄ et flot f , capacité(S →

S̄) ≥ valeur(f ). Dès lors, pour toute coupe capacité(S → S̄) ≥ fmax et pour
tout flot, coupemin ≥ valeur(f ) et en particulier coupemin ≥ fmax . On a donc

capacité(S → S̄) ≥ coupemin ≥ fmax ≥ valeur(f )

d’où capacité(S → S̄) = coupemin et fmax = valeur(f ) en cas d’égalité

capacité(S → S̄) = valeur(f ).

On va montrer quelque chose d’encore plus fort : la valeur du flot maxi-

mum est toujours égal à la capacité de la coupe minimum. Pour cela, on a
besoin de quelques définitions supplémentaires.

Définition 10.8. Etant donné un flot f , à tout chemin P dans le graphe

non-dirigé sous-jacent associons la quantité i(P ) = mina∈P i(a), où i(a) =
c(a) − f (a) pour les arêtes a prises par P dans le sens direct, et i(a) = f (a)
pour les arêtes a prises dans le sens inverse.
Un chemin P est f -saturé si i(P ) = 0. Il est f -augmentant s’il est non
saturé, part d’un noeud source et arrive à un noeud puits.

73
 De manière intuitive, l’intérêt d’un chemin f -augmentant est que l’on
peut augmenter la valeur du flot f en faisant passer plus de flot le long de ce
chemin. En effet, un nouveau flot valide peut être obtenu en faisant la mise à
jour f (e) ← f (e) + i(P ) pour les arêtes en sens direct, et f (e) ← f (e) − i(P )
pour les arêtes en sens inverse. La valeur du flot est ainsi augmentée de i(P ).
Exemple 10.9. Sur le flot f figure 3 on a un chemin f -augmentant SABCDT :
en effet il va de la source S au puits T et est non-saturé car i(SA) = 5−1 = 4
(sens direct), i(AB) = 2 (sens inverse), i(BC) = 1, i(CD) = 2, i(DT ) = 4
et donc i(SABCDT ) = 1. On peut dès lors créer un nouveau flot f 0 valide
qui augmente la valeur du flot de 1, donc valeur(f 0 ) = valeur(f ) + 1. Le flot
est alors modifié le long de ce chemin comme montré à la figure 4. Notre
chemin est maintenant f 0 -saturé, on ne peut plus augmenter le flot le long
de ce chemin (l’arête BC a atteint sa capacité maximale).

A C T

1/5 2/3 3/4 2/2 0/4

S B D

Figure 3 – Chemin f -augmentant. Note : seul le sous-graphe associé au

chemin f -augmenté est représenté et non le graphe complet, sinon le flot ne
serait pas correct (le flot net des noeuds intermédiaires est non nul).

A C T

2/5 1/3 4/4 1/2 1/4

S B D

Figure 4 – Chemin avec f 0 . Il est f 0 -saturé.

Théorème 10.10. Un flot est maximum si et seulement si il ne contient

pas de chemin f -augmentant.

Démonstration. Montrons un sens à la fois

⇒ Supposons par l’absurde qu’il existe un chemin f -augmentant dans
un flot maximal f . Alors on peut améliorer strictement le flot le long
de ce chemin augmentant, ce qui contredit l’hypothèse d’optimalité
de f .
⇐ Soit f un flot qui ne contient pas de chemin f -augmentant. Soit S
l’ensemble des noeuds qu’on peut atteindre à partir de la source avec

74
 des chemins non f -saturés. S ne contient aucun puits, sinon on aurait
un chemin f -augmentant. Soit une arête de S → S̄, elle est f -saturée
par construction de S, sinon la destination de l’arête serait dans S.
Soit une arête de S̄ → S, elle doit être f -nulle pour la même raison.
Dès lors,

A 4/4 a

S T

B 0/5 b

Figure 5 – En bleu, l’ensemble S et en vert, l’ensemble S̄

capacité(S → S̄) = valeur du flot qui quitte S vers S̄

= valeur du flot net entre S et S̄
= valeur(f ),

et par le corollaire 10.7 on a donc que cette coupe est la coupe mini-
num et ce flot est le flot maximum.

Théorème 10.11 (“Max Flow = Min Cut”). La valeur du flot maximum

et la capacité de la coupe minimum sont toujours égales, donc

fmax = coupemin .

Démonstration. On a déjà prouvé dans le corollaire 10.7 que la capacité

de la coupe minimale est toujours supérieure ou égale à la valeur du flot
maximum, on montre ici qu’il est toujours possible de trouver une coupe
de capacité égale au flot maximum. En utilisant la preuve du théorème
précédent, on a une méthode qui montre comment du flot maximum on
déduit une coupe minimale de même valeur. Il faut construire S l’ensemble
des noeuds atteignables depuis les sources par des chemins non f -saturés,
et la coupe minimale est donc donnée par S → S̄.

10.2 L’algorithme de Ford-Fulkerson

Les résultats précédents suggèrent une méthode pour trouver le flot maxi-
mum dans un réseau : il suffit d’augmenter le flot en trouvant des chemins
augmentants, jusqu’à ce que cela ne soit plus possible : c’est ce que fait
l’algorithme de Ford-Fulkerson.

75
Algorithme 10.12 (Algorithme de Ford-Fulkerson). L’algorithme de Ford-
Fulkerson permet de determiner le flot maximum d’un graphe. Partant d’un
flot initial arbitraire f , on cherche un chemin f -augmentant et on augmente
le flot grâce à ce chemin, jusqu’à ce qu’il n’y ait plus de chemin augmentant
ce qui veut dire que le flot est optimal. Pour trouver le chemin augmentant on
peut, par exemple, créer un graphe auxilière, ou chaque arête est remplacée
par une arête dans le même sens portant la capacité encore disponible (le flot
qu’on peut ajouter, càd c(e) − f (e)) et un arête retour portant la quantité
qu’on peut retirer sur cette arrête (le flot qu’on peut retirer, càd f (e)). Il
suffit ensuite de chercher un chemin partant d’une source vers un puits dans
le graphe auxilière pour trouver un chemin augmentant associé.

Lemme 10.13. Dans tout graphe dirigé avec un noeud source u et un noeud
puits v et chaque arête de capacité unitaire, le nombre maximum de chemins
dirigés de u vers v disjoints deux à deux par les arêtes est la valeur du flot
maximum.

76
11 P, N P et N P-complétude
11.1 P, N P et N P-complétude
Définition 11.1. Un problème de décision est une liste d’objets finis appelés
instances, chacune porteuse d’un label OUI ou NON. Donc c’est une fonction
des instances vers l’ensemble {OUI, NON}. Les instances positives sont celles
de label OUI.
Un algorithme résout un problème de décision donné s’il prend en entrée une
instance du problème et renvoie en sortie le label OUI ou NON correspondant
à l’instance.

Définition 11.2. La taille d’une instance est le nombre de bits nécessaire

pour décrire l’instance. Pour un graphe, on considère souvent que c’est son
nombre d’arêtes ou son nombre de noeuds.

Définition 11.3. Un algorithme est efficace ou polynomial s’il produit une

réponse en un temps borné par un polynôme de la taille de l’entrée.

Définition 11.4. La classe P est la classe des problèmes pour lesquels il

existe un algorithme efficace qui les résout.
Cette classe contient par exemple le problème du graphe eulérien.

Définition 11.5. Un problème est dans N P s’il existe un algorithme efficace

A tel que :
— pour chaque instance positive m, il existe un objet fini n tel que
A(m, n) renvoie OUI,
— pour chaque instance négative m et tout objet fini n, A(m, n) renvoie
NON.

Exemple 11.6. Problème du graphe hamiltonien :

m = graphe non-dirigé = instance

n = cycle dans m = “preuve” ou “témoin”
A(m, n) = OUI ssi n est hamiltonien.

Corollaire 11.7. P ⊆ N P

Démonstration. C’est par définition de l’ensemble. On verra à la fin de cette

section qu’il pourrait (bien qu’il est peu probable) prouver que P = N P

77
Définition 11.8. Etant donnés deux problèmes P et Q, on dit que P est
réductible en temps polynomial à Q, ou que P est réductible à Q, ou plus
informellement que P est plus facile que Q, noté P ≤ Q, s’il existe un
algorithme efficace A (appelé réduction) qui prenne en entrée une instance
n de P et renvoie en sortie une instance A(n) de Q, telle que n est positive
ssi A(n) est positive.

Exemple 11.9. Soit les problèmes suivant

Problème COUPLAGE-PARFAIT
Instance Graphe non-dirigé
Question Existe-t-il un couplage parfait ?
Problème POLYÈDRE-NON-VIDE
Instance Inégalité Ax ≤ b (géométriquement : polyèdre {x ∈ Rm : Ax ≤
b})
Question Le polyèdre est-il non vide ? C’est à dire, ∃x : Ax ≤ b ?
COUPLAGE-PARFAIT ≤ POLYÈDRE-NON-VIDE

Démonstration. Soit M la matrice d’incidence du graphe. Il existe un cou-

1
 
m  .. 
plage parfait si et seulement si ∃x ∈ {0, 1} tel que M x =  .  si et
1
seulement si (il faut admettre le sens “seulement si”, le sens “si” est trivial)
1
 
n  .. 
∃x ∈ R tel que M x =  .  et 0 ≤ xi ≤ 1. Ce qui est un cas particulier de
1
la question “∃x : Ax ≤ b ?” Fabriquer A et b à partir du graphe se fait en
temps polynomial en la taille du graphe.

Donc : Tout algo pour résoudre POLYÈDRE-NON-VIDE peut être uti-

lisé pour résoudre COUPLAGE-PARFAIT.

Théorème 11.10. Si P ≤ Q et Q ∈ P alors P ∈ P.

Démonstration. Cette preuve n’a pas été vue.

Exemple 11.11. Soit les problèmes suivant

Problème k-CLIQUE
Instance Graphe
Question Existe-t-il une clique à k noeuds ?
k-CLIQUE ≤ k-INDEPENDANT ≤ k-CLIQUE. Ils sont donc équivalents.

78
Définition 11.12. On dit qu’un problème P est N P-complet si P ∈ N P
et pour tout problème Q ∈ N P, Q ≤ P .
C’est donc un problème de N P plus difficile que tous les autres.

Théorème 11.13 (Cook). SAT est N P-complet.

Exemple 11.14. Soit le problème suivant

Problème SAT
Instance Formule logique
Question Existe-t-il des valeurs de vérité pour les variables telles que la
formule est vraie.
Par exemple, l’instance ¬(P ∨ Q) ∧ (R ∨ ¬Q) est une instanc epositive car
(R, P, Q) = (VRAI, FAUX, FAUX) vérifie la formule.

Théorème 11.15 (Karp). Déterminer si un graphe est hamiltonien est

N P-complet.

Démonstration. — HAMILTONIEN ∈ N P : trivial.

— Il existe une réduction de SAT vers HAMILTONIEN (partie difficile
de la preuve) donc SAT ≤ HAMILTONIEN.
Donc HAMILTONIEN est N P-complet. On a d’ailleurs SAT = HAMIL-
TONIEN car SAT est N P-complet.

Théorème 11.16 (Comment prouver qu’un problème P est N P-complet ?). Démonstration. 1.
Prouver P ∈ N P ;
2. Choisir un problème Q connu comme N P − complet ;
3. Prouver Q ≤ P en exhibant une réduction efficace.

Définition 11.17. On pourrait essayer de prouver que P = N P si et seule-

ment si on montrait qu’un problème N P (Hamilton, SAT ou encore le su-
doku) ∈ P

Exemple 11.18. Quelques problèmes N P-complets en théorie des graphes :

— k-CLIQUE
— k-COUVERTURE
— k-INDEPENDANT
— HAMILTONIEN
— k-COLORABILITE
— k-ARETE-COLORABILITE
— COUPE-MAX
— VOYAGEUR DE COMMERCE

79
Exemple 11.19. k-INDEPENDANT est N P-complet.
La réduction de 3-SAT vers k-INDEPENDANT sur un exemple :

(¬x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ ¬x2 ∨ ¬x3 ) ∧ (x1 ∨ x2 ∨ x3 )

donne

x1 ¬x2 ¬x3

¬x1 x1

x2 x2

x3 x3

80