CAHIERS DE LA CRM

Introduction la
thorie des graphes
Didier Mller
CAHIER N
O
6 COMMISSION ROMANDE DE MATHMATIQUE
Table des matires
Avant-propos 1
But de ce fascicule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Corrigs des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Logiciels pour les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1 Graphes non orients 3
1.1 Premires dnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Reprsentation graphique . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Quelques types de graphes . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Exemple dutilisation dun graphe pour rsoudre un problme . . 4
1.1.4 Graphes dintervalles . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Graphe partiel et sous-graphe . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Degrs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Degr dun sommet . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Degr dun graphe . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Chanes et cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Graphes eulriens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Graphes hamiltoniens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Couplages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1 Calcul dun couplage maximum . . . . . . . . . . . . . . . . . . 13
1.8 Graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.9 Reprsentations non graphiques dun graphe . . . . . . . . . . . . . . . . 15
1.9.1 Matrice dadjacences . . . . . . . . . . . . . . . . . . . . . . . . 15
1.9.2 Listes dadjacences . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.10 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.10.1 Codage de Prfer . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.11 Arbres couvrants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.11.1 Arbre couvrant de poids minimum . . . . . . . . . . . . . . . . . 20
1.12 Coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.12.1 Encadrement du nombre chromatique . . . . . . . . . . . . . . . 21
1.12.2 Algorithme de coloration de Welsh et Powell . . . . . . . . . . . 24
1.12.3 Graphes parfaits . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.12.4 Coloration des sommets dun graphe planaire . . . . . . . . . . . 24
1.12.5 Coloration des artes dun graphe . . . . . . . . . . . . . . . . . 25
1.13 Graphes trianguls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2 Graphes orients 29
2.1 Graphes orients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Degr dun sommet dun digraphe . . . . . . . . . . . . . . . . . . . . . 29
2.3 Chemins et circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.1 Digraphe fortement connexe . . . . . . . . . . . . . . . . . . . . 31
2.4 Reprsentations non graphiques des digraphes . . . . . . . . . . . . . . . 31
2.4.1 Matrice dadjacences . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.2 Listes dadjacences . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5 Digraphes sans circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6 Graphes de comparabilit . . . . . . . . . . . . . . . . . . . . . . . . . . 34
CAHIERS DE LA CRM N
o
6 i
2.7 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.8 Rseau PERT (Project Evaluation and Review Technique) . . . . . . . . . 37
Bibliographie 40
Lexique 41
Index 46
ii N
o
6 CAHIERS DE LA CRM
Avant-propos
La mise en oeuvre du RRM a ncessit certains ajustements des programmes de mathma-
tiques enseigns dans les gymnases de Suisse romande. La Commission Romande de Ma-
thmatique (CRM) tient proposer des moyens denseignement conformes aux exigences
du rglement de maturit. Aussi ses membres semploient-ils depuis plusieurs annes la
mise jour de sa collection Ouvrages collectifs qui couvrent en priorit les besoins du
programme de niveau standard.
Certaines notions gnralement tudies dans les cours de mathmatiques de niveau ren-
forc ont t volontairement retires des ouvrages de base. En outre, lintroduction des
options spciques a ouvert de nouveaux horizons quant aux sujets de mathmatiques
abords. Soucieuse de tenir compte de cette volution, la CRM proposait en 2004 les deux
premiers ouvrages dune nouvelle collection, les Cahiers de la CRM.
Ce cahier, le sixime de la srie, parle des graphes, un sujet inhabituel dans les cours tra-
ditionnels de mathmatiques et qui sintgre parfaitement bien dans une Option Spcique
ou dans une Option Complmentaire.
La CRM est heureuse de prsenter aujourdhui un ouvrage sortant des sentiers battus :
Introduction la thorie des graphes
de Didier Mller
Les ouvrages publis ces dernires annes par la CRM sont marqus par le souci dtre ac-
cessibles la lecture individuelle des lves. Jespre quil en ira de mme pour cet ouvrage
et que vous aurez grand plaisir vous plonger dans ce monde fascinant des graphes.
Tous mes remerciements Didier Mller pour stre lanc dans laventure de la publication
dun cahier, ainsi quaux membres de la CRM qui ont consacr de leur temps une lecture
nale minutieuse.
Patrick Hochuli
Prsident de la CRM
Dcembre 2011
But de ce fascicule
Le but de ce fascicule est dinitier les lycens la thorie des graphes.
Je nai pas pour ambition de faire une thorie complte, mais de montrer comment les
graphes peuvent tre une mthode de rsolution de problmes intressante.
Ce cours se veut accessible aux lves de lyce, car il ne demande pratiquement pas de
connaissances pralables. Il est dcoup en deux parties principales : les graphes non orien-
ts et les graphes orients.
Comme la thorie des graphes utilise un jargon bien particulier, le dbut du cours comporte
beaucoup de dnitions. Cest un peu rbarbatif, mais indispensable pour la suite. Un index
et un lexique en n de fascicule aideront llve assimiler ces termes.
Les exercices sont essentiellement de deux types :
Des exercices thoriques sur les graphes, qui sont souvent des dmonstrations assez
simples, gnralement par induction, ou par labsurde ; il y a aussi des exercices de
rexion qui permettent de se rendre compte si on a bien compris un concept ou non.
Des exercices pratiques o il peut tre avantageux dutiliser des graphes pour modliser
et rsoudre un problme.
CAHIERS DE LA CRM N
o
6 1
Corrigs des exercices
Par manque de place dans ce fascicule, les corrigs des exercices sont disponibles gratuite-
ment sur le site www.nymphomath.ch/graphes. Linternaute trouvera galement sur ce site
quelques applets pour illustrer certains concepts.
Logiciels pour les graphes
Le logiciel gratuit Grin 4.0 (pour Windows) permet entre autres de :
dessiner des graphes
produire la matrice dadjacences daprs le dessin
colorer des graphes
trouver le plus court chemin dans un graphe
trouver les cycles eulriens et hamiltoniens
Bref, ce logiciel est un complment idal ce cours ! Il a t crit par Vitali Petchenkine et
est disponible ladresse web : www.nymphomath.ch/graphes/logiciel/ (la page ofcielle
de ce programme a disparu du web).
Mathematica permet aussi de travailler avec les graphes. Voir [5] dans la bibliographie.
Pour aller plus loin
Pour en savoir beaucoup plus sur les graphes, voici quelques livres que jai utiliss, classs
du plus simple au plus complet :
Alain Hertz propose une initiation aux graphes sous forme dnigmes policires [3]. Cela
illustre bien comment les graphes peuvent tre utiles pour modliser des problmes.
Thorie des graphes [1] donne une base solide, tout en restant accessible au plus grand
nombre. Trs agrable lire. Un regret : pas dexercices.
Les graphes par lexemple [2] est comme [1] accessible des lycens, mais il contient
en plus des exercices corrigs.
Introduction to graph theory [6] est trs complet, mais dun niveau universitaire et en
anglais.
Graphes et algorithmes [4] est un indmodable, de niveau universitaire et malheureuse-
ment trs cher.
Didier Mller
2 N
o
6 CAHIERS DE LA CRM
1 Graphes non orients
1.1 Premires dnitions
Un graphe ni G = (V, E) est dni par lensemble ni V ={v
1
, v
2
, . . . , v
n
} dont les l-
ments sont appels sommets (Vertices en anglais), et par lensemble ni E ={e
1
, e
2
, . . . , e
m
}
dont les lments sont appels artes (Edges en anglais).
Une arte e de lensemble E est dnie par une paire non ordonne de sommets, appels
les extrmits de e. Si larte e relie les sommets a et b, on dira que ces sommets sont
adjacents, ou incidents avec e, ou bien que larte e est incidente avec les sommets a
et b.
On appelle ordre dun graphe le nombre de sommets n de ce graphe.
1.1.1 Reprsentation graphique
Les graphes tirent leur nom du fait quon peut les reprsenter par des dessins. chaque
sommet de G, on fait correspondre un point distinct du plan et on relie les points corres-
pondant aux extrmits de chaque arte. Il existe donc une innit de reprsentations dun
graphe. Les artes ne sont pas forcment rectilignes.
Si on peut dessiner un graphe G dans le plan sans quaucune arte nen coupe une autre (les
artes ne sont pas forcment rectilignes), on dit que G est planaire. Le graphe G ci-dessus
est planaire.
1
2
5
3
4
Une reprsentation non planaire du
graphe G (des artes se croisent)
1 5
4
3
2
Une reprsentation planaire de G
1.1.2 Quelques types de graphes
Un graphe est simple si au plus une arte relie deux sommets et sil ny a pas de boucle sur
un sommet. On peut imaginer des graphes avec une arte qui relie un sommet lui-mme
(une boucle), ou plusieurs artes reliant les deux mmes sommets. On appelera ces graphes
des multigraphes.
1
2 4
3
Multigraphe
CAHIERS DE LA CRM N
o
6 3
Un graphe est connexe sil est possible, partir de nimporte quel sommet, de rejoindre
tous les autres en suivant les artes. Un graphe non connexe se dcompose en composantes
connexes. Sur le graphe ci-dessous, les composantes connexes sont {1, 2, 3, 4} et {5, 6}.
2 1
3 6
4 5
Graphe non connexe
V ={1, 2, 3, 4, 5, 6}
E =
_
{1, 3}, {1, 4}, {2, 3}, {3, 4}, {5, 6}
_
Un graphe est complet si chaque sommet du graphe est reli directement tous les autres
sommets.
1
2
5
3
4
Graphe complet K
5
V ={1, 2, 3, 4, 5}
E =
_
{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3},
{2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}
_
Un graphe est biparti si ses sommets peuvent tre diviss en deux ensembles X et Y ,
de sorte que toutes les artes du graphe relient un sommet dans X un sommet dans Y
(dans lexemple ci-dessous, on a X ={1, 3, 5} et Y ={2, 4}, ou vice versa).
1
2
3
4
5
Graphe biparti
V ={1, 2, 3, 4, 5}
E =
_
{1, 2}, {1, 4}, {2, 5}, {3, 4}, {4, 5}
_
1.1.3 Exemple dutilisation dun graphe pour rsoudre un problme
On a six wagons trier. Dans la gare de triage, les wagons entrent dans lordre 2, 5, 3, 6,
1, 4 et doivent sortir dans lordre croissant. Deux wagons i et j peuvent tre mis sur la
mme voie si et seulement sils entrent dans lordre dans lequel ils doivent sortir.
Dessinez un graphe illustrant la situation, en indiquant ce que reprsentent les sommets et
les artes de votre graphe. Quel sera le nombre minimal de voies ncessaires au tri ?
Solution
On reprsente les wagons par les sommets. Une arte relie
deux sommets i et j si les wagons i et j ne peuvent pas
tre sur la mme voie. On obtient le graphe ci-contre.
On voit que 1, 3 et 5 ne peuvent pas tre sur la mme voie.
Il faut donc trois voies au minimum.
2 1
3 6
4 5
4 N
o
6 CAHIERS DE LA CRM
Exercice 1
Trois professeurs P
1
, P
2
, P
3
devront donner lundi prochain un certain nombre dheures de
cours trois classes C
1
, C
2
, C
3
:
P
1
doit donner 2 heures de cours C
1
et 1 heure C
2
;
P
2
doit donner 1 heure de cours C
1
, 1 heure C
2
et 1 heure C
3
;
P
3
doit donner 1 heure de cours C
1
, 1 heure C
2
et 2 heures C
3
.
Comment reprsenter cette situation par un graphe ? Quel type de graphe obtenez-vous ?
Combien faudra-t-il de plages horaires au minimum?
Aidez-vous du graphe pour proposer un horaire du lundi pour ces professeurs.
Exercice 2
Un tournoi dchecs oppose 6 personnes. Chaque joueur doit affronter tous les autres.
Construisez un graphe reprsentant toutes les parties possibles.
Quel type de graphe obtenez-vous ?
Si chaque joueur ne joue quun match par jour, combien de jours faudra-t-il pour terminer
le tournoi ?
Aidez-vous du graphe pour proposer un calendrier des matches.
Exercice 3
Sur un chiquier 33, les deux cavaliers noirs sont placs sur les cases a1
et c1, les deux cavaliers blancs occupant les cases a3 et c3.
Aidez-vous dun graphe pour dterminer les mouvements alterns des blancs
et des noirs qui permettront aux cavaliers blancs de prendre les places des
cavaliers noirs, et vice versa. Les blancs commencent.
1.1.4 Graphes dintervalles
On construit un graphe G partir des intervalles de la droite relle I
1
, . . . , I
n
, o les som-
mets de G sont numrots de 1 n. Dans un graphe dintervalles, il existe une arte entre
les sommets i et j , i = j , si et seulement si I
i
I
j
=.
Autrement dit, deux sommets sont relis si et seulement si les deux intervalles correspon-
dants se chevauchent.
CAHIERS DE LA CRM N
o
6 5
Exercice 4
Cet exercice est inspir de la nouvelle de Claude Berge Qui a tu le Duc de Densmore
(Bibliothque Oulipienne n

67, 1994, Rdition Castor Astral, 2000). Dans cette nouvelle

policire, le lecteur peut dcouvrir le meurtrier grce un thorme combinatoire d au
mathmaticien hongrois G. Hajs.
Un jour, Sherlock Holmes reoit la visite de son ami Watson que lon avait charg den-
quter sur un assassinat mystrieux datant de plus de trois ans.
lpoque, le Duc de Densmore avait t tu par lexplosion dune bombe, qui avait en-
tirement dtruit le chteau de Densmore o il stait retir. Les journaux dalors relataient
que le testament, dtruit lui aussi dans lexplosion, avait tout pour dplaire lune de ses
sept ex-pouses. Or, avant de mourir, le Duc les avait toutes invites passer quelques jours
dans sa retraite cossaise.
Holmes : Je me souviens de cette affaire ; ce qui est trange, cest que la bombe avait t
fabrique spcialement pour tre cache dans larmure de la chambre coucher, ce qui
suppose que lassassin a ncessairement effectu plusieurs visites au chteau !
Watson : Certes, et pour cette raison, jai interrog chacune des femmes : Ann, Betty,
Charlotte, Edith, Flicia, Georgia et Helen. Elles ont toutes jur quelles navaient t au
chteau de Densmore quune seule fois dans leur vie.
Holmes : Hum! Leur avez-vous demand quelle priode elles ont eu leur sjour respectif ?
Watson : Hlas ! Aucune ne se rappelait les dates exactes, aprs plus de trois ans ! Nan-
moins, je leur ai demand qui elles avaient rencontr :
Ann a rencontr Betty, Charlotte, Flicia et Georgia.
Betty a rencontr Ann, Charlotte, Edith, Flicia et Helen.
Charlotte a rencontr Ann, Betty et Edith.
Edith a rencontr Betty, Charlotte et Flicia.
Flicia a rencontr Ann, Betty, Edith et Helen.
Georgia a rencontr Ann et Helen.
Helen a rencontr Betty, Flicia et Georgia.
Vous voyez, mon cher Holmes, les rponses sont concordantes !
Cest alors que Holmes prit un crayon et dessina un trange petit dessin, avec des points
marqu A, B, C, E, F, G, H et des lignes reliant certains de ces points. Puis, en moins de
trente secondes, Holmes dclara :
Tiens, tiens ! Ce que vous venez de me dire dtermine dune faon unique lassassin.
Qui est lassassin ?
1.2 Graphe partiel et sous-graphe
Soit G = (V, E) un graphe. Le graphe G

= (V, E

) est un graphe partiel de G, si E

est inclus dans E. Autrement dit, on obtient G

en enlevant une ou plusieurs artes au

graphe G.
Pour un sous-ensemble de sommets A inclus dans V , le sous-graphe de G induit par A
est le graphe G =
_
A, E(A)
_
dont lensemble des sommets est A et lensemble des artes
E(A) est form de toutes les artes de G ayant leurs deux extrmits dans A. Autrement
dit, on obtient G

en enlevant un ou plusieurs sommets au graphe G, ainsi que toutes les

artes incidentes ces sommets.
6 N
o
6 CAHIERS DE LA CRM
2 1
3 6
4 5
Graphe G
V ={1, 2, 3, 4, 5, 6}
E =
_
{1, 3}, {1, 4}, {2, 3},
{3, 4}, {4, 5}, {5, 6}
_
2 1
3 6
4 5
Graphe partiel de G
V ={1, 2, 3, 4, 5, 6}
E =
_
{1, 3}, {1, 4},
{2, 3}, {5, 6}
_
2 1
3 6
5
Sous-graphe de G
V ={1, 2, 3, 5, 6}
E =
_
{1, 3}, {2, 3}, {5, 6}
_
Un graphe partiel dun sous-graphe est un sous-graphe partiel de G. On appelle clique
un sous-graphe complet de G. Dans le graphe G ci-dessus, le sous-graphe K = (V, E),
avec V ={1, 3, 4} et E =
_
{1, 3}, {1, 4}, {3, 4}
_
est une clique.
Exercice 5
Montrez que dans un groupe form de six personnes, il y en a ncessairement trois qui
se connaissent mutuellement ou trois qui ne se connaissent pas (on suppose que si A
connat B, B connat galement A).
Montrez que cela nest plus ncessairement vrai dans un groupe de cinq personnes.
1.3 Degrs
1.3.1 Degr dun sommet
On appelle degr du sommet v, et on note d(v), le nombre dartes incidentes ce sommet.
Attention ! Une boucle sur un sommet compte double.
Dans un graphe simple, on peut aussi dnir le degr dun sommet comme tant le nombre
de ses voisins (la taille de son voisinage).
Dans le multigraphe ci-contre, on a les degrs :
d(v
1
) = 2
d(v
2
) = 2
d(v
3
) = 4
d(v
4
) = 1
d(v
5
) = 3
v
1
v
2
v
5
v
3
v
4
Thorme 1.1 (Lemme des poignes de mains)
La somme des degrs des sommets dun graphe est gale deux fois le nombre dartes.
Exercice 6
Dmontrez le lemme des poignes de mains.
CAHIERS DE LA CRM N
o
6 7
1.3.2 Degr dun graphe
Le degr dun graphe est le degr maximum de tous ses sommets. Dans lexemple ci-
dessous, le degr du graphe est 4, cause du sommet v
3
.
v
1
v
2
v
5
v
3
v
4
Un graphe dont tous les sommets ont le mme degr est dit rgulier. Si le degr commun
est k, alors on dit que le graphe est k-rgulier.
Exercice 7
Montrez quun graphe simple a un nombre pair de sommets de degr impair.
Exercice 8
Montrez que dans une assemble de n personnes, il y a toujours au moins 2 personnes qui
ont le mme nombre damis prsents.
Exercice 9
Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit reli avec exacte-
ment trois autres ?
Exercice 10
On sintresse aux graphes 3-rguliers. Construisez de tels graphes ayant 4, 5, 6, puis 7
sommets. Quen dduisez-vous ? Prouvez-le !
Exercice 11
Une suite dcroissante (au sens large) dentiers est graphique sil existe un graphe simple
dont les degrs des sommets correspondent cette suite. Par exemple, un triangle corres-
pond la suite (2, 2, 2). Les suites suivantes sont-elles graphiques ?
1) (3, 3, 2, 1, 1)
2) (3, 3, 1, 1)
3) (3, 3, 2, 2)
4) (4, 2, 1, 1, 1, 1)
5) (5, 3, 2, 1, 1, 1)
6) (5, 4, 3, 1, 1, 1, 1)
Trouvez deux graphes correspondant la suite (3, 2, 2, 2, 1).
1.4 Chanes et cycles
Une chane dans G, est une suite ayant pour lments alternativement des sommets et des
artes, commenant et se terminant par un sommet, et telle que chaque arte est encadre
par ses extrmits.
8 N
o
6 CAHIERS DE LA CRM
On dira que la chane relie le premier sommet de la suite au dernier sommet. En plus, on
dira que la chane a pour longueur le nombre dartes de la chane.
Le graphe ci-dessous contient entre autres les chanes (v
1
, e
1
, v
2
, e
2
, v
3
, e
5
, v
5
)
et (v
4
, e
4
, v
3
, e
2
, v
2
, e
1
, v
1
).
v
1
v
2
v
5
v
3
v
4
e
1
e
3
e
2
e
5
e
4
On ne change pas une chane en inversant lordre des lments dans la suite correspondante.
Ainsi, les chanes (v
1
, e
3
, v
3
, e
4
, v
4
) et (v
4
, e
4
, v
3
, e
3
, v
1
) sont identiques.
Exercice 12
Dans certains livres, on dnit une chane comme une suite de sommets. Pour quel type de
graphe cette dnition nest-elle pas adquate ?
On appelle distance entre deux sommets la longueur de la plus petite chane les reliant.
On appelle diamtre dun graphe la plus longue des distances entre deux sommets.
Une chane est lmentaire si chaque sommet y apparat au plus une fois.
Une chane est simple si chaque arte apparat au plus une fois. Dans le graphe prcdent,
(v
1
, e
1
, v
2
, e
2
, v
3
) est une chane simple et lmentaire.
Une chane dont les sommets de dpart et de n sont les mmes est appele chane ferme.
Dans le graphe prcdent, (v
4
, e
4
, v
3
, e
5
, v
5
, e
5
, v
3
, e
4
, v
4
) est une chane ferme.
Une chane ferme simple est appele cycle. Dans le graphe prcdent, la chane
(v
1
, e
1
, v
2
, e
2
, v
3
, e
3
, v
1
) est un cycle.
Exercice 13
Quels sont les graphes de diamtre 1 ?
Thorme 1.2
Un graphe est biparti si et seulement sil ne contient aucun cycle de longueur impaire.
Exercice 14
Dmontrez le thorme 1.2.
Exercice 15
Montrez que ce graphe est biparti :
1 2
3 4
5 6
7 8
CAHIERS DE LA CRM N
o
6 9
Thorme 1.3
Pour un graphe G ayant m artes, n sommets et p composantes connexes, on dnit :
(G) = mn+ p
(G) est appel le nombre cyclomatique. Prononcer nu de G.
On a (G) 0 pour tout graphe G.
De plus, (G) = 0 si et seulement si G est sans cycle.
Exercice 16
Dmontrez le thorme 1.3.
1.5 Graphes eulriens
On appelle cycle eulrien dun graphe G un cycle passant une et une seule fois par chacune
des artes de G. Un graphe est dit eulrien sil possde un cycle eulrien.
On appelle chane eulrienne dun graphe G une chane passant une et une seule fois par
chacune des artes de G. Un graphe ne possdant que des chanes eulriennes est semi-
eulrien.
Plus simplement, on peut dire quun graphe est eulrien (ou semi-eulrien) sil est possible
de dessiner le graphe sans lever le crayon et sans passer deux fois sur la mme arte.
Exercice 17
Cet exercice est un des problmes fondateurs de la thorie des graphes, propos par le
mathmaticien suisse Leonhard Euler en 1736.
En 1652, la ville de Knigsberg (aujourdhui Kaliningrad) possde sept ponts enjambant
la Pregel, qui coule de part et dautre de lle de Kneiphof.
Knigsberg en 1652
Au cours dune promenade, est-il possible de passer sur tous les ponts de la ville une et une
seule fois ?
10 N
o
6 CAHIERS DE LA CRM
Exercice 18
Donnez un critre permettant de dire coup sr si un graphe est eulrien.
Exercice 19
Les graphes suivants sont-ils eulriens (ou semi-eulriens) ?
2 1
3 6
4 5
1
2
5
3
4
1
2
3
4
5
Exercice 20
Soit G un graphe non eulrien. Est-il toujours possible de rendre G eulrien en lui rajoutant
un sommet et quelques artes ?
Exercice 21
Est-il possible de tracer une courbe, sans lever le crayon, qui coupe chacun des 16 segments
de la gure suivante exactement une fois ?
Exercice 22
On considre des dominos dont les faces sont numrotes 1, 2, 3, 4 ou 5.
1) En excluant les dominos doubles, de combien de dominos dispose-t-on ?
2) Montrez que lon peut arranger ces dominos de faon former une boucle ferme (en
utilisant la rgle habituelle de contact entre les dominos).
3) Pourquoi nest-il pas ncessaire de considrer les dominos doubles ?
4) Si lon prend maintenant des dominos dont les faces sont numrotes de 1 n, est-il
possible de les arranger de faon former une boucle ferme ?
1.6 Graphes hamiltoniens
On appelle cycle hamiltonien dun graphe G un cycle passant une et une seule fois par
chacun des sommets de G. Un graphe est dit hamiltonien sil possde un cycle hamilto-
nien.
On appelle chane hamiltonienne dun graphe G une chane passant une et une seule fois
par chacun des sommets de G. Un graphe ne possdant que des chanes hamiltoniennes est
semi-hamiltonien.
Contrairement aux graphes eulriens, il nexiste pas de caractrisation simple des graphes
(semi-)hamiltoniens. On peut noncer quelques proprits et conditions sufsantes :
CAHIERS DE LA CRM N
o
6 11
un graphe possdant un sommet de degr 1 ne peut pas tre hamiltonien ;
si un sommet dans un graphe est de degr 2, alors les deux artes incidentes ce sommet
doivent faire partie du cycle hamiltonien ;
les graphes complets K
n
sont hamiltoniens.
Thorme 1.4 (Ore)
Soit G un graphe simple dordre n 3. Si pour toute paire {x, y} de sommets non
adjacents, on a d(x) +d(y) n, alors G est hamiltonien.
Corollaire 1.5 (Dirac)
Soit G un graphe simple dordre n 3. Si pour tout sommet x de G, on a d(x)
n
2
,
alors G est hamiltonien.
En effet, un tel graphe vrie les conditions du thorme prcdent, car si x et y ne sont
pas adjacents, on a bien : d(x) +d(y)
n
2
+
n
2
= n.
Exercice 23
Dessinez un graphe dordre au moins 5 qui est. . .
1) hamiltonien et eulrien
2) hamiltonien et non eulrien
3) non hamiltonien et eulrien
4) non hamiltonien et non eulrien.
Exercice 24
Un club de 9 joueurs se runit chaque jour autour dune table ronde. Une rgle du club
interdit quun joueur ait deux fois la mme personne ct de lui.
1) Combien de jours au maximum pourront-ils se runir en satisfaisant cette rgle ?
2) Donnez une organisation de la table pour chacun de ces jours.
3) Mme question que 1), mais avec 3 tables de 3 places.
4) Donnez une organisation des trois tables pour chacun de ces jours.
Exercice 25
Huit personnes se retrouvent pour un repas de mariage. Le graphe ci-dessous prcise les
incompatibilits dhumeur entre ces personnes (une arte reliant deux personnes indique
quelles ne se supportent pas).
A B
H C
G D
F E
12 N
o
6 CAHIERS DE LA CRM
Proposez un plan de table (la table est ronde) en vitant de placer cte cte deux personnes
incompatibles.
1.7 Couplages
Soit G un graphe simple. Un couplage C de G est un sous-graphe partiel 1-rgulier de G.
On peut aussi dire quun couplage (ou appariement) est un ensemble dartes deux deux
non-adjacentes.
Un sommet v est satur par un couplage C si v est lextrmit dune arte de C. Dans le
cas contraire, v est insatur.
Un couplage maximum est un couplage contenant le plus grand nombre possible dartes.
Un graphe peut possder plusieurs couplages maximum.
1
2
5
3
4
En gras, un couplage maximum de G. Les sommets 1, 3, 4 et 5 sont saturs.
Un couplage parfait est un couplage o chaque sommet du graphe est satur.
1 2
3 4
5 6
Un couplage
1 2
3 4
5 6
Un couplage maximum et parfait
1.7.1 Calcul dun couplage maximum
Si C est un couplage de G, on appelle chane alterne une chane lmentaire de G dont
les artes sont alternativement dans C et hors de C.
Une chane alterne est dite augmentante si elle relie deux sommets insaturs. Ci-dessus,
gauche, la chane 1-4-3-6 est augmentante. En intervertissant les paisseurs des artes
le long de cette chane, on obtient un meilleur couplage (ci-dessus, droite).
Thorme 1.6 (Berge, 1957)
Un couplage C est maximum si et seulement sil nexiste pas de chane augmentante
relativement C.
Exercice 26
Une assemble est forme de personnes parlant plusieurs langues diffrentes (voir tableau
ci-aprs). On veut former des binmes de personnes qui pourront dialoguer entre elles.
Comment maximiser le nombre de binmes ?
CAHIERS DE LA CRM N
o
6 13
Allemand Anglais Arabe Chinois Franais Espagnol Russe
Alfred $ $
Bernard $ $
Claude $ $
Denis $
Ernest $
Fabien $ $ $
Georges $ $
Henri $ $ $
Isidore $ $
Joseph $ $
Kurt $ $
Louis $
Exercice 27
Une entremetteuse essaie de former le plus de couples possible avec 6 lles et 6 garons
en fonction de critres esthtiques et de compatibilit dhumeur. Elle a dress le tableau
dincompatibilits ci-aprs, o une croix indique que deux personnes sont incompatibles.
Combien de couples pourra-t-elle former au maximum?
Anne Batrice Carine Drew Elonore Florie
Alfred $ $ $ $
Bernard $
Claude $ $ $ $
Denis $ $ $
Ernest $ $
Fabien $ $ $ $
1.8 Graphes planaires
On dit quun graphe est planaire si on peut le dessiner dans le plan de sorte que ses artes
ne se croisent pas. Rappelons que les artes ne sont pas forcment rectilignes.
Une carte, ou graphe planaire topologique, est une reprsentation particulire dun mul-
tigraphe planaire ni. On dit quune carte est connexe si son graphe lest. Une carte divise
le plan en plusieurs rgions.
Par exemple, la carte ci-dessous, avec sept sommets et neuf artes, divise le plan en quatre
rgions (A, B,C, D). Trois rgions sont limites alors que la quatrime (D), extrieure au
diagramme, ne lest pas.
1 5
6
2 3 7
4
A
B
C
D
14 N
o
6 CAHIERS DE LA CRM
Le degr dune rgion r, not d(r), est la longueur de la chane ferme minimum pas-
sant par tous les sommets qui dlimitent cette rgion. Dans le graphe ci-dessus, d(A) = 6
(la rgion A est dlimite par la chane ferme passant par les sommets (1, 2, 3, 5, 6, 5, 1)),
d(B) = 4, d(C) = 3 et d(D) = 5.
On remarque que toute arte limite deux rgions, ou est contenue dans une rgion et est
alors compte deux fois dans la chane ferme. Nous avons donc un lemme pour les rgions,
analogue au lemme des poignes de mains pour les sommets.
Thorme 1.7
La somme des degrs des rgions dune carte connexe est gale deux fois le nombre
dartes.
On peut vrier ce thorme sur le graphe prcdent : il comporte 9 artes et la somme des
degrs des rgions vaut 18.
Thorme 1.8 (Euler, 1752)
Euler a tabli une formule clbre qui relie le nombre de sommets S, le nombre
dartes A et le nombre de rgions R dune carte connexe :
SA+R = 2
Exercice 28
Dmontrez le thorme dEuler en procdant par rcurrence sur les sommets.
Thorme 1.9 (Kuratowski, 1930)
Un graphe est non planaire si et seulement sil contient un sous-graphe homomorphe
(voir lexique) au graphe biparti K
3,3
ou au graphe complet K
5
.
1
2
3
4
5
6
1
2
5
3
4
Exercice 29
Utilisez le thorme dEuler pour dmontrer que le graphe biparti K
3,3
nest pas planaire.
1.9 Reprsentations non graphiques dun graphe
1.9.1 Matrice dadjacences
On peut reprsenter un graphe simple par une matrice dadjacences. Une matrice (nm)
est un tableau de n lignes et m colonnes. (i, j) dsigne lintersection de la ligne i et de
CAHIERS DE LA CRM N
o
6 15
la colonne j . Dans une matrice dadjacences, les lignes et les colonnes reprsentent les
sommets du graphe. Un 1 la position (i, j) signie que le sommet i est adjacent au
sommet j .
1 5
4
3
2
M =
_
_
_
_
_
_
0 0 1 1 1
0 0 1 0 0
1 1 0 1 1
1 0 1 0 1
1 0 1 1 0
_
_
_
_
_
_
Cette matrice a plusieurs caractristiques :
1. Elle est carre : il y a autant de lignes que de colonnes.
2. Il ny a que des zros sur la diagonale allant du coin suprieur gauche au coin inf-
rieur droit. Un 1 sur la diagonale indiquerait une boucle.
3. Elle est symtrique : m
i j
=m
ji
. On peut dire que la diagonale est un axe de symtrie.
4. Une fois que lon xe lordre des sommets, il existe une matrice dadjacences unique
pour chaque graphe. Celle-ci nest la matrice dadjacences daucun autre graphe.
Exercice 30
On a calcul ci-dessous les matrices M
2
et M
3
(M est la matrice ci-dessus). Pour chacune
de ces matrices, quoi correspondent les nombres obtenus ?
M
2
=
_
_
_
_
_
_
3 1 2 2 2
1 1 0 1 1
2 0 4 2 2
2 1 2 3 2
2 1 2 2 3
_
_
_
_
_
_
M
3
=
_
_
_
_
_
_
6 2 8 7 7
2 0 4 2 2
8 4 6 8 8
7 2 8 6 7
7 2 8 7 6
_
_
_
_
_
_
1.9.2 Listes dadjacences
On peut aussi reprsenter un graphe simple en donnant pour chacun de ses sommets la liste
des sommets auxquels il est adjacent. Ce sont les listes dadjacences.
1 5
4
3
2
1 : 3, 4, 5
2 : 3
3 : 1, 2, 4, 5
4 : 1, 3, 5
5 : 1, 3, 4
Exercice 31
Dcrivez le graphe G ci-dessous par une matrice dadjacences et des listes dadjacences.
7 2 1
5
3 4 6
16 N
o
6 CAHIERS DE LA CRM
1.10 Arbres
On appelle arbre tout graphe connexe sans cycle. Un graphe sans cycle mais non connexe
est appel une fort.
Une feuille ou sommet pendant est un sommet de degr 1.
2 1
3 6
4 5
Arbre
Les sommets 1, 2 et 5 sont les feuilles
2 1
3 6
4 5
Fort
Les sommets 1, 2, 5 et 6 sont les feuilles
Thorme 1.10
Les afrmations suivantes sont quivalentes pour tout graphe G n sommets.
1. G est un arbre,
2. G est sans cycle et connexe,
3. G est sans cycle et comporte n1 artes,
4. G est connexe et comporte n1 artes,
5. chaque paire u, v de sommets distincts est relie par une seule chane simple (et
le graphe est sans boucle).
Exercice 32
Dmontrez le thorme 1.10. Pour cela, utilisez le thorme 1.3.
Thorme 1.11
Tout arbre ni avec au moins deux sommets comporte au moins deux sommets
pendants.
Exercice 33
Dmontrez le thorme 1.11.
Exercice 34
Combien darbres diffrents existe-t-il avec 5 sommets ? avec 6 sommets ? avec 7 som-
mets ?
Exercice 35
Dmontrez quun arbre a au plus un couplage parfait. Quelle est la condition ncessaire
et sufsante pour quun arbre T ait un couplage parfait ?
CAHIERS DE LA CRM N
o
6 17
1.10.1 Codage de Prfer
Le codage de Prfer (1918) est une manire trs compacte de dcrire un arbre. Il a t
propos par le mathmaticien allemand Ernst Paul Heinz Prfer (1896-1934).
Codage
Soit larbre T = (V, E) et supposons V ={1, 2, . . . , n}.
Lalgorithme ci-dessous fournira le code de T , cest--dire une suite S de n 2 termes
employant (ventuellement plusieurs fois) des nombres choisis parmi 1, . . . , n.
Pas gnral de lalgorithme de codage
( rpter tant quil reste plus de deux sommets dans larbre T )
1. identier la feuille v de larbre ayant le numro minimum;
2. ajouter la suite S le seul sommet s adjacent v dans larbre T ;
3. enlever de larbre T le sommet v et larte incidente v.
Exemple de codage
2 3 4
1 5 6
S ={}
2 3 4
5 6
S ={2}
3 4
5 6
S ={2, 3}
3
5 6
S ={2, 3, 3}
3
6
S ={2, 3, 3, 3}
Il reste 2 sommets :
n du codage
Dcodage
Donne : suite S de n2 nombres, chacun provenant de {1, . . . , n}.
Posons I ={1, . . . , n}.
Pas gnral de lalgorithme de dcodage
( rpter tant quil reste des lments dans S et plus de deux lments dans I )
1. identier le plus petit lment i de I napparaissant pas dans la suite S ;
2. relier par une arte de T le sommet i avec le sommet s correspondant au premier
lment de la suite S ;
3. enlever i de I et s de S.
Les deux lments qui restent dans I la n de lalgorithme constituent les extrmits de
la dernire arte ajouter T .
18 N
o
6 CAHIERS DE LA CRM
Exemple de dcodage
2 3 4
1 5 6
S ={2, 3, 3, 3}
I ={1, 2, 3, 4, 5, 6}
2 3 4
1 5 6
S ={3, 3, 3}
I ={2, 3, 4, 5, 6}
2 3 4
1 5 6
S ={3, 3}
I ={3, 4, 5, 6}
2 3 4
1 5 6
S ={3}
I ={3, 5, 6}
2 3 4
1 5 6
S ={}
I ={3, 6}
2 3 4
1 5 6
S ={}
I ={}
Exercice 36
Trouvez le codage de Prfer de larbre ci-dessous.
1 2 6 8 10
4 3 5 7 9
Exercice 37
Dessinez larbre correspondant la suite S ={1, 1, 1, 1, 1, 1, 1, 1}.
Thorme 1.12 (Cayley, 1857)
Le nombre darbres que lon peut construire sur n (n 2) sommets numrots est
gal n
n2
.
Exercice 38
Dmontrez le thorme 1.12. Utilisez le codage de Prfer.
1.11 Arbres couvrants
1
2
5
3
4
Graphe G
1
2
5
3
4
Un arbre couvrant
Un arbre couvrant (aussi appel arbre maximal) est un graphe partiel qui est aussi un
arbre.
Exercice 39
Combien darbres couvrants diffrents le graphe G ci-dessus possde-t-il ?
CAHIERS DE LA CRM N
o
6 19
1.11.1 Arbre couvrant de poids minimum
Soit le graphe G = (V, E) avec un poids associ chacune de ses artes. On veut trouver,
dans G, un arbre maximal A = (V, F) de poids total minimum.
Algorithme de Kruskal (1956)
Donnes :
Graphe G = (V, E) (|V| = n, |E| = m)
Pour chaque arte e de E, son poids c(e).
Rsultat : Arbre ou fort maximale A = (V, F) de poids minimum.
Trier et renumroter les artes de G dans lordre croissant de leur poids :
c(e
1
) c(e
2
) . . . c(e
m
).
Poser F :=, k := 0
Tant que k < m et |F| < n1 faire
Dbut
si e
k+1
ne forme pas de cycle avec F alors F := F {e
k+1
}
k := k +1
Fin
Exemple
1 2 3
4 5 6
5
3
2
4
5
2
1
1 3
1 2 3
4 5 6
1
1 2 3
4 5 6
1
1
1 2 3
4 5 6
2
1
1
1 2 3
4 5 6
2
1
1
2
1 2 3
4 5 6
4
2
1
1
2
Les artes de poids 3 nont pas pu tre places, car elles auraient form un cycle.
Lalgorithme sest arrt ds que cinq artes ont t places. Toute arte supplmentaire
aurait cr un cycle.
Sil y a plusieurs artes de mme poids, il peut y avoir plusieurs arbres couvrants de poids
minimum : tout dpend de lordre dans lequel ces artes ont t tries.
Exercice 40
Trouvez tous les arbres couvrants de poids minimum du graphe ci-aprs (les chiffres sur
les artes reprsentent leur poids).
v
1
v
6
v
2
v
7
v
5
v
3
v
4
1
2
2
2
2
3
5
2
2
1
1
3
20 N
o
6 CAHIERS DE LA CRM
1.12 Coloration
Soit G = (V, E) un graphe. Un sous-ensemble S de V est un stable sil ne comprend que
des sommets non adjacents deux deux. Dans le graphe ci-dessous, {v
1
, v
2
} forment un
stable ; {v
2
, v
4
} aussi, ainsi que {v
2
, v
5
} et {v
3
, v
5
}.
Le cardinal du plus grand stable est le nombre de stabilit de G ; on le note (G). Dans
le graphe ci-dessous, on a (G)=2.
v
1
v
2
v
5
v
3
v
4
La coloration des sommets dun graphe consiste affecter tous les sommets de ce graphe
une couleur de telle sorte que deux sommets adjacents ne portent pas la mme couleur. Une
coloration avec k couleurs est donc une partition de lensemble des sommets en k stables.
Le nombre chromatique du graphe G, not (G), est le plus petit entier k pour lequel il
existe une partition de V en k sous-ensembles stables.
Sur le graphe ci-dessous, on a eu besoin de trois couleurs (notes 1, 2 et 3) pour colorer les
sommets de sorte que deux sommets adjacents aient des couleurs diffrentes. On a donc
trois stables : {v
1
, v
2
}, {v
3
, v
5
} et {v
4
}. On ne peut pas utiliser moins de couleurs, cause
des cliques {v
1
, v
4
, v
5
} et {v
1
, v
3
, v
4
}.
v
1
v
2
v
5
v
3
v
4
1
2
3
2
1
Remarquons enn que le sommet v
2
aurait aussi pu tre color 3 . La coloration mini-
male nest donc pas forcment unique.
1.12.1 Encadrement du nombre chromatique
Majoration
(G) r +1, o r est le plus grand degr des sommets de G.
Preuve : Soit un graphe et r le degr maximum de ses sommets. Donnons-nous une
palette de (r +1) couleurs. Pour chaque sommet du graphe on peut tenir le raisonne-
ment suivant : ce sommet est adjacent r sommets au plus, et le nombre de couleurs
dj utilises pour colorer ces sommets est donc infrieur ou gal r. Il reste donc au
moins une couleur non utilise dans la palette, avec laquelle nous pouvons colorer notre
sommet.
(G) n+1(G)
Preuve : Considrons S un stable de V de cardinalit (G). Une coloration possible
des sommets consiste colorer les sommets de S dune mme couleur et les n (G)
autres sommets de couleurs toutes diffrentes. On en dduit que (G) 1+(n(G)).
CAHIERS DE LA CRM N
o
6 21
Minoration
Le nombre chromatique dun graphe est suprieur ou gal celui de chacun de ses
sous-graphes.
Preuve : Ce rsultat dcoule de la dnition mme du nombre chromatique.
Le nombre chromatique du graphe sera suprieur ou gal lordre de sa plus grande
clique, que lon note (G) (prononcer omga de G). Autrement dit, (G) (G)
Preuve : Puisque, par dnition, dans une clique dordre m, tous les sommets sont
adjacents entre eux, il faudra m couleurs. Donc, il faudra au moins (G) couleurs pour
colorer le graphe G.
Exercice 41
Majorez et minorez le nombre chromatique de ce graphe.
v
1
v
6
v
2
v
7
v
5
v
3
v
4
Exercice 42
On donne un graphe de 7 sommets par sa matrice dadjacences M ci-dessous. Ce graphe
reprsente les 7 bancs dun parc et les alles permettant de passer de lun lautre.
M =
_
_
_
_
_
_
_
_
_
_
0 1 0 0 0 0 1
1 0 0 0 1 1 0
0 0 0 1 1 0 0
0 0 1 0 1 0 0
0 1 1 1 0 1 1
0 1 0 0 1 0 0
1 0 0 0 1 0 0
_
_
_
_
_
_
_
_
_
_
1. On veut peindre les bancs de faon que deux bancs relis par une alle soient toujours
de couleurs diffrentes. Donnez un encadrement du nombre minimal de couleurs
ncessaire, en justiant. Dterminez ce nombre.
2. Est-il possible de parcourir toutes les alles de ce parc sans passer deux fois par la
mme alle ?
3. Est-il possible de parcourir des alles de ce parc en passant ct de chaque banc
exactement une fois ?
Exercice 43
Sept lves, dsigns par A, B, C, D, E, F et G, se sont rendus la bibliothque aujourdhui.
Le tableau suivant prcise qui a rencontr qui (la bibliothque tant petite, deux lves
prsents au mme moment se rencontrent ncessairement...).
llve A B C D E F G
a rencontr D,E D,E,F,G E,G A,B,E A,B,C,D,F,G B,E,G B,C,E,F
22 N
o
6 CAHIERS DE LA CRM
De combien de places assises doit disposer la bibliothque pour que chacun ait pu travailler
correctement au cours de cette journe ?
Exercice 44
Sept agences de voyage proposent des visites de monuments et lieux emblmatiques de
Saint-Ptersbourg : la cathdrale Saint-Isaac, le Muse de lErmitage, le Muse russe et la
forteresse Pierre et Paul. Un mme lieu ne peut pas tre visit par plusieurs groupes de
compagnies diffrentes le mme jour.
La premire compagnie fait visiter uniquement la cathdrale Saint-Isaac ; la seconde la
cathdrale Saint-Isaac et le Muse russe ; la troisime la forteresse Pierre et Paul ; la qua-
trime le Muse russe et la forteresse Pierre et Paul ; la cinquime la cathdrale Saint-Isaac
et le Muse de lErmitage ; la sixime le Muse de lErmitage et la forteresse Pierre et
Paul ; la septime le Muse russe et le Muse de lErmitage.
Ces agences peuvent-elles organiser les visites sur les trois premiers jours de la semaine ?
Exercice 45
Un lyce doit organiser les horaires des examens. On suppose quil y a 7 preuves pla-
nier, correspondant aux cours numrots de 1 7 et que les paires de cours suivantes ont
des tudiants communs : 1 et 2, 1 et 3, 1 et 4, 1 et 7, 2 et 3, 2 et 4, 2 et 5, 2 et 7, 3 et 4, 3
et 6, 3 et 7, 4 et 5, 4 et 6, 5 et 6, 5 et 7 et enn 6 et 7.
Comment organiser ces preuves de faon quaucun tudiant nait passer deux preuves
en mme temps et cela sur une dure minimale ?
Exercice 46
On veut transporter des produits chimiques par le rail. A, B, C, D, E, F, G et H dsignent
huit produits chimiques. Dans le tableau ci-dessous, une croix signie que les produits ne
peuvent pas tre entreposs dans le mme wagon, car il y aurait risque dexplosion :
A B C D E F G H
A $ $ $ $ $
B $ $ $ $
C $ $ $ $ $
D $ $ $ $
E $ $ $ $
F $ $ $
G $ $ $ $
H $ $ $
Quel nombre minimum de wagons faut-il ?
Exercice 47
Tout graphe contenant un triangle (K
3
) ne peut pas tre color en moins de trois couleurs.
1. Construire un graphe sans K
3
qui ncessite galement trois couleurs.
2. Comment, partir du graphe prcdent, construire un graphe sans K
4
ncessitant 4
couleurs ?
3. Comment construire un graphe sans K
5
ncessitant 5 couleurs ?
CAHIERS DE LA CRM N
o
6 23
Exercice 48
Exprimez la rsolution dun Sudoku classique en termes de coloration de graphe. Dcrivez
le graphe (nombre de sommets, nombre dartes, etc.). Combien faut-il de couleurs ?
1.12.2 Algorithme de coloration de Welsh et Powell
Cet algorithme couramment utilis permet dobtenir une assez bonne coloration dun
graphe, cest--dire une coloration nutilisant pas un trop grand nombre de couleurs.
Cependant il nassure pas que le nombre de couleurs soit minimum (et donc gal au nombre
chromatique du graphe).
tape 1
Classer les sommets du graphe dans lordre dcroissant de leur degr, et attribuer chacun
des sommets son numro dordre dans la liste obtenue.
tape 2
En parcourant la liste dans lordre, attribuer une couleur non encore utilise au premier
sommet non encore color, et attribuer cette mme couleur chaque sommet non encore
color et non adjacent un sommet de cette couleur.
tape 3
Sil reste des sommets non colors dans le graphe, revenir ltape 2. Sinon, FIN.
Exercice 49
Utilisez lalgorithme de coloration de Welsh et Powell pour colorer les graphes des exer-
cices 41, 44 et 45.
1.12.3 Graphes parfaits
Dans le cadre de la thorie des graphes, Claude Berge a introduit en 1960 la notion de
graphe parfait comme dnissant un graphe pour lequel le nombre chromatique de chaque
sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont gaux.
Un graphe G est donc parfait si pour tout sous-graphe induit G

de G on a (G

) =(G

).
1.12.4 Coloration des sommets dun graphe planaire
Thorme 1.13 (Thorme des quatre couleurs)
On peut colorer les sommets dun graphe planaire (sans boucles) en utilisant au plus
quatre couleurs de telle sorte que toutes les artes aient des extrmits de couleurs
diffrentes.
Cette conjecture a t formule pour la premire fois par lcossais Francis Guthrie en 1852.
Il tait alors question de coloration de carte de gographie (voir exercice 51). La preuve
de ce thorme narriva quen... 1976, grce Kenneth Appel et Wolfgang Haken. La d-
monstration t grand bruit car ce fut le premier thorme de lhistoire des mathmatiques
qui a ncessit lusage systmatique de lordinateur.
Exercice 50
Colorez cet oeuf et le billet pos dessus avec le moins de couleurs possibles, en faisant en
sorte que deux rgions voisines aient des couleurs diffrentes.
24 N
o
6 CAHIERS DE LA CRM
Combien de couleurs donne lalgorithme de Welsh et Powell ?
Exercice 51
Colorez la carte des communes dAjoie ci-dessous en utilisant le moins de couleurs pos-
sibles, de sorte que deux rgions voisines aient des couleurs diffrentes.
Construisez dabord un graphe associ cette carte, puis colorez-en les sommets.
1.12.5 Coloration des artes dun graphe
La coloration des artes dun graphe consiste affecter toutes les artes de ce graphe une
couleur de telle sorte que deux artes adjacentes ne portent pas la mme couleur.
Lindice chromatique du graphe G est le plus petit entier k pour lequel il existe une
coloration des artes ; on le note (G).
Pour colorer les artes dun graphe, on peut se ramener au problme de la coloration des
sommets. Il suft pour cela de travailler non pas sur le graphe lui-mme, mais sur le graphe
adjoint, not G

, et que lon dnit ainsi :

1. chaque arte de G = (V, E) correspond un sommet de G

= (E, F)
2. deux sommets de G

sont relis par une arte si les deux artes correspondantes de G

sont adjacentes.
CAHIERS DE LA CRM N
o
6 25
v
1
v
2
v
5
v
3
v
4
e
1
e
3
e
2
e
5
e
4
e
6
Graphe G
e
1
e
2
e
6
e
3
e
5
e
4
Graphe adjoint G

e
1
e
2
e
6
e
3
e
5
e
4
2
3
4
1
2
1
Graphe adjoint G

color
On peut ensuite appliquer lalgorithme de Welsh et Powell sur le graphe G

pour colorer
ses sommets. Une fois cela fait, on colorera les artes de G de la mme couleur que les
sommets correspondants de G

.
Exercice 52
Dans un tournoi dchecs, chaque joueur doit rencontrer tous les autres. Chaque partie dure
une heure. Dterminez la dure minimum du tournoi dans le cas o le nombre de joueurs
est 3, 4, 5 ou 6.
1.13 Graphes trianguls
Un graphe est triangul si tous ses cycles de plus de 3 sommets contiennent au moins une
corde (arte reliant deux sommets non adjacents dun cycle).
Un sparateur est un sous-ensemble W de sommets dans un graphe connexe G = (V, E)
tel que le graphe G[V W] est non connexe. Dans le graphe ci-dessous, W ={v
1
, v
4
} est
un sparateur, W ={v
3
} est un sparateur minimal.
v
1
v
2
v
5
v
3
v
4
Un sommet v est dit simplicial si son voisinage N(v) est une clique. Dans le graphe ci-
dessus, les sommets simpliciaux sont v
2
et v
5
.
Thorme 1.14
Un graphe connexe est triangul si et seulement si tout sparateur minimal est une
clique.
Preuve
1. Supposons tout dabord que tout sparateur est une clique. Soit C = [x
1
, x
2
, . . . , x
k
, x
1
]
(k 4) un cycle dans G et soit W un sparateur minimal de x
1
et x
3
. W doit contenir x
2
et au moins un des sommets x
4
,. . . , x
k
. Comme W est une clique, il existe une corde
dans C.
26 N
o
6 CAHIERS DE LA CRM
2. Supposons G triangul et soit W un sparateur minimal. Supposons que W ne soit
pas une clique. Soient G
1
= (V
1
, E
1
) et G
2
= (V
2
, E
2
) deux composantes connexes de
G[V W] et soient x et y deux sommets non adjacents dans W . Comme W est minimal,
x et y ont chacun au moins un voisin dans G
1
et dans G
2
. Soient a
1
et a
2
les voisins
de x dans G
1
et G
2
, et soient b
1
et b
2
ceux de y dans G
1
et G
2
. Comme G
1
et G
2
sont connexes, il existe une chane reliant a
1
b
1
dans G
1
et une chane reliant a
2
b
2
dans G
2
. Il existe donc une chane C
1
sans corde reliant x y dans G[V
1
W] ainsi
quune chane sans corde C
2
reliant x y dans G[V
2
W] . Lunion de C
1
et C
2
est un
cycle sans corde contenant au moins 4 sommets, contradiction.
2
Thorme 1.15
Tout graphe triangul autre quune clique contient au moins deux sommets simpliciaux
non adjacents.
Preuve
Si G ne contient que deux sommets, alors G est constitu de deux sommets isols qui
sont simpliciaux non adjacents. Supposons donc le thorme vrai pour tout graphe ayant
moins de n sommets et soit |V| = n. Soit W un sparateur minimal et G
1
= (V
1
, E
1
)
et G
2
= (V
2
, E
2
) deux composantes connexes de G[V W] . On a vu que W est une clique.
Si G[V
1
W] est une clique alors choisissons x dans V
1
: x est simplicial dans G[V
1
W] .
Sinon, par hypothse dinduction, il existe deux sommets simpliciaux non adjacents dans
G[V
1
W] , et comme W est une clique, lun de ces sommets quon appellera x est
dans V
1
.
Dans chacun des deux cas on a dtermin un sommet x simplicial dans G[V
1
W] . De
mme, on peut dterminer un sommet y simplicial dans G[V
2
W] . Ces deux sommets x
et y sont simpliciaux dans G et non-adjacents.
2
Algorithme de reconnaissance (Fulkerson et Gross, 1969)
1. Poser G

= G ;
2. Si G

est vide alors G est triangul : STOP

3. Si G

ne contient pas de sommet simplicial alors G nest pas triangul.

4. ter un sommet simplicial de G

et retourner 2.
Exercice 53
Appliquez lalgorithme de Fulkerson et Gross pour vrier que le graphe ci-dessous est
triangul.
v
1
v
2
v
3
v
8
v
4
v
5
v
6
v
7
CAHIERS DE LA CRM N
o
6 27
Un schma dlimination parfait est un ordre v
1
< . . . < v
n
des sommets tel que v
i
est
simplicial dans G[v
i
, . . . , v
n
] (n =|V| ).
Thorme 1.16
Un graphe est triangul si et seulement sil possde un schma dlimination parfait.
Preuve
1. Soit v
1
< . . . < v
n
un schma dlimination parfait et soit C = [x
1
, x
2
, . . . , x
k
, x
1
] (k 4)
un cycle dans G. Sans perte de gnralit, on peut supposer que x
1
= v
i
apparat avant
x
2
, . . . , x
k
dans le schma dlimination parfait. Mais alors x
2
est reli x
k
car x
1
est
simplicial dans le graphe G[v
i
, . . . , v
n
] qui contient x
2
, . . . , x
k
. Le cycle C a donc une
corde.
2. Si G est triangul on peut dterminer un schma dlimination parfait comme suit :
Poser i :=1 ;
Tant que V = faire
Choisir un sommet simplicial x dans le graphe rsiduel. Mettre x en position i
ter x de V et poser i := i +1
2
Exercice 54
Montrez que les arbres, les graphes complets et les graphes dintervalles sont des graphes
trianguls.
Algorithme de coloration dun graphe triangul G=(V,E)
Dterminer un schma dlimination parfait v
1
< . . . < v
n
Colorer G squentiellement selon lordre inverse v
n
< . . . < v
1
, en utilisant pour chaque
sommet le plus petit numro de couleur possible.
Exercice 55
Donnez un schma dlimination parfait du graphe ci-dessous et colorez ce graphe.
v
1
v
2
v
3
v
8
v
4
v
5
v
6
v
7
28 N
o
6 CAHIERS DE LA CRM
2 Graphes orients
2.1 Graphes orients
En donnant un sens aux artes dun graphe, on obtient un digraphe (ou graphe orient).
Le mot digraphe est la contraction de lexpression anglaise directed graph .
Un digraphe ni G = (V, E) est dni par lensemble ni V ={v
1
, v
2
, . . . , v
n
} dont les l-
ments sont appels sommets, et par lensemble ni E ={e
1
, e
2
, . . . , e
m
} dont les lments
sont appels arcs.
Un arc e de lensemble E est dni par une paire ordonne de sommets. Lorsque e = (u, v),
on dit que larc e va de u v. On dit aussi que u est lextrmit initiale et v lextrmit
nale de e.
Exercice 56
Construire un graphe orient dont les sommets sont les entiers compris entre 1 et 12 et dont
les arcs reprsentent la relation tre diviseur de .
2.2 Degr dun sommet dun digraphe
Soit v un sommet dun graphe orient.
On note d
+
(v) le degr extrieur du sommet v, cest--dire le nombre darcs ayant v
comme extrmit initiale.
On note d

(v) le degr intrieur du sommet v, cest--dire le nombre darcs ayant v

comme extrmit nale.
On dnit le degr :
d(v) = d
+
(v) +d

(v)
Exercice 57
Trouvez les degrs extrieurs et intrieurs de chacun des sommets du graphe ci-dessous :
2 1
3 6
4 5
2.3 Chemins et circuits
Un chemin conduisant du sommet a au sommet b est une suite ayant pour lments alter-
nativement des sommets et des arcs, commenant et se terminant par un sommet, et telle
que chaque arc est encadr gauche par son sommet origine et droite par son sommet
destination. On ne peut donc pas prendre les arc rebours. Sur le digraphe ci-aprs, on
peut voir par exemple le chemin (v
3
, e
2
, v
2
, e
1
, v
1
). Par convention, tout chemin comporte
au moins un arc.
On appelle distance entre deux sommets dun digraphe la longueur du plus petit chemin
les reliant. Sil nexiste pas de chemin entre les sommets x et y, on pose d(x, y) = .
Par exemple, sur le digraphe ci-dessous, d(v
5
, v
4
) = 2, d(v
4
, v
5
) = , d(v
3
, v
1
) = 1,
CAHIERS DE LA CRM N
o
6 29
v
1
v
2
v
5
v
3
v
4
e
1
e
3
e
2
e
5
e
4
Un circuit est un chemin dont les sommets de dpart et de n sont les mmes. Le digraphe
ci-dessus ne contient pas de circuit.
Les notions de chemins et de circuits sont analogues celles des chanes et des cycles pour
les graphes non orients.
Exercice 58
Soit X un ensemble de lapins, et G un graphe orient ayant X pour ensemble de sommets.
On dit que G est un graphe de parent si les arcs de G codent la relation tre le parent
de... . Quelles conditions doit ncessairement vrier G pour pouvoir tre un graphe de
parent ?
Exercice 59
On souhaite prlever 4 litres de liquide dans un tonneau. Pour cela, nous avons notre
disposition deux rcipients (non gradus !), lun de 5 litres, lautre de 3 litres.
Comment doit-on procder ?
Exercice 60 (Jeu de Fan Tan)
Deux joueurs disposent de plusieurs tas dallumettes. tour de rle, chaque joueur peut
enlever un certain nombre dallumettes de lun des tas (selon la rgle choisie). Le joueur
qui retire la dernire allumette perd la partie.
Modlisez ce jeu laide dun graphe dans le cas o lon dispose au dpart de deux tas
contenant chacun trois allumettes, et o un joueur peut enlever une ou deux allumettes
chaque fois. Que doit jouer le premier joueur pour gagner la partie coup sr ?
Exercice 61
On appelle tournoi un digraphe complet.
1. Montrez que tout tournoi ayant 3 sommets admet un chemin hamiltonien.
2. Soit T un tournoi ayant n1 sommets et un chemin hamiltonien x
1
, x
2
, . . . , x
n2
, x
n1
.
On suppose que lon ajoute un sommet x
n
ce graphe et que, pour chaque sommet
x
1
, x
2
, . . . , x
n2
, x
n1
, on ajoute soit un arc (x
n
, x
j
), soit un arc (x
j
, x
n
), 1 j < n, de
faon former un tournoi T

sans chemin hamiltonien. Dans quels sens sont alors orien-

ts les arcs entre x
1
et x
n
et entre x
n1
et x
n
? Est-il possible davoir un arc orient
de x
j
vers x
n
et un autre de x
n
vers x
j+1
pour 1 j < n 1 ? En dduire que T

a
ncessairement un chemin hamiltonien.
3. Dduisez des questions 1 et 2 que tout tournoi admet un chemin hamiltonien.
Exercice 62
Dans un digraphe, un roi est un sommet duquel tous les autres sommets sont une distance
dau plus 2.
Dmontrez quun tournoi a toujours un roi (Landau, 1953).
30 N
o
6 CAHIERS DE LA CRM
2.3.1 Digraphe fortement connexe
Un digraphe est fortement connexe, si toute paire ordonne (a, b) de sommets distincts du
graphe est relie par au moins un chemin. En dautres termes, tout sommet est atteignable
depuis tous les autres sommets par au moins un chemin.
On appelle composante fortement connexe tout sous-graphe induit maximal fortement
connexe (maximal signie quil ny a pas de sous-graphe induit connexe plus grand conte-
nant les sommets de la composante).
Exercice 63
Donnez un algorithme permettant de calculer la distance entre deux sommets x et y dun
digraphe connexe.
Exercice 64
Proposez un algorithme qui dtermine si un graphe est fortement connexe ou non.
Indication : utilisez un systme de marquage des sommets.
Les graphes ci-dessous sont-il fortement connexes ? Si non, donnez leurs composantes
fortement connexes.
v
9
v
10
v
11
v
12
v
5
v
6
v
7
v
8
v
1
v
2
v
3
v
4
v
13
v
14
v
15
v
16
v
9
v
10
v
11
v
12
v
5
v
6
v
7
v
8
v
1
v
2
v
3
v
4
2.4 Reprsentations non graphiques des digraphes
2.4.1 Matrice dadjacences
On peut reprsenter un digraphe par une matrice dadjacences. Une matrice (nm) est
un tableau de n lignes et m colonnes. (i, j) dsigne lintersection de la ligne i et de la
colonne j .
Dans une matrice dadjacences, les lignes et les colonnes reprsentent les sommets du
graphe. Un 1 la position (i, j ) signie quun arc part de i pour rejoindre j .
Exemple
Voici la matrice dadjacences du digraphe G :
2 1
3 6
4 5
M =
_
_
_
_
_
_
_
_
0 1 0 1 0 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 1 0 0 0 0
_
_
_
_
_
_
_
_
CAHIERS DE LA CRM N
o
6 31
Cette matrice a plusieurs caractristiques :
1. Elle est carre : il y a autant de lignes que de colonnes.
2. Il ny a que des zros sur la diagonale. Un 1 sur la diagonale indiquerait une
boucle.
3. Contrairement celle dun graphe non orient, elle nest pas symtrique.
4. Une fois que lon xe lordre des sommets, il existe une matrice dadjacences unique
pour chaque digraphe. Celle-ci nest la matrice dadjacences daucun autre digraphe.
Exercice 65
On a calcul ci-dessous les matrices M
2
et M
3
. M est la matrice dadjacences du graphe
de lexemple.
Pour chacune de ces matrices, quoi correspondent les nombres obtenus ?
M
2
=
_
_
_
_
_
_
_
_
0 1 0 1 2 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 1 0
_
_
_
_
_
_
_
_
M
3
=
_
_
_
_
_
_
_
_
0 0 0 1 2 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
_
_
_
_
_
_
_
_
2.4.2 Listes dadjacences
On peut aussi reprsenter un digraphe en donnant pour chacun de ses sommets la liste des
sommets quon peut atteindre directement en suivant un arc (dans le sens de la che).
Exemple
Voici les listes dadjacences du digraphe G :
2 1
3 6
4 5
1 : 2, 4, 6
2 : 4, 5
3 : 4
4 : 5
5 :
6 : 2
Exercice 66
Dcrivez le graphe G ci-dessous par une matrice dadjacences et des listes dadjacences.
7 2 1
5
3 4 6
32 N
o
6 CAHIERS DE LA CRM
2.5 Digraphes sans circuit
Thorme 2.1
Le digraphe G est sans circuit si et seulement si on peut attribuer un nombre r(v),
appel le rang de v, chaque sommet v de manire que pour tout arc (u, v) de G on ait
r(u) < r(v).
Preuve
Si G comporte un circuit C, il nest pas possible de trouver de tels nombres r(i) car,
autrement, considrant r( j) = max{r(i) | i C} et larc ( j, k) C, on aurait r( j) r(k)
en contradiction avec la dnition du rang.
Rciproquement, si G na pas de circuit, il existe au moins un sommet sans prdcesseur
dans G (sans cela, en remontant successivement dun sommet un prdcesseur, on nirait
par fermer un circuit). Ainsi, on peut attribuer squentiellement des valeurs aux sommets
du graphe laide de lalgorithme qui suit, ce qui conclura la dmonstration.
2
Algorithme de calcul du rang
Donne : digraphe G = (V, E) sans circuit.
Rsultat : rang r(v) de chaque sommet v V du digraphe G.
Dbut
r := 0
X :=V
R : lensemble des sommets de X sans prdcesseur dans X
Tant que X nest pas vide faire
r(v) := r pour tout sommet v R
X := X R
R : lensemble des sommets de X sans prdcesseur dans X
r := r +1
Fin tant que
Fin
Exercice 67
Attribuez un rang aux sommets du digraphe ci-dessous en utilisant lalgorithme de calcul
du rang.
7 2 1 8
5
3 4 6
CAHIERS DE LA CRM N
o
6 33
2.6 Graphes de comparabilit
Un graphe est de comparabilit si on peut orienter ses artes de faon transitive, cest--
dire de telle sorte que sil existe un arc de i vers j et un arc de j vers k, alors il existe
galement un arc de i vers k.
Algorithme permettant de dterminer si G=(V,E) est un graphe de comparabilit
1. F :=
2. Tant que F = E faire
Choisir une arte e dans E F, donner une orientation e et complter cette
orientation pour assurer une orientation transitive de G.
Si une arte doit tre oriente dans les deux sens, STOP :
G nest pas de comparabilit.
Sinon, rajouter F toutes les artes nouvellement orientes. Si F = E alors
STOP :
G est de comparabilit.
Exemple
1 2
3
5 6
1 2
3
5 6
Jusque l, tout va bien. . .
1 2
3
5 6
Ae. Il manque une arte
entre les sommets 3 et 2.
Exercice 68
Les graphes ci-dessous admettent-ils une orientation transitive ?
1 2
3 4
5 6
1
2 3
4 5 6
Etant donn quune orientation transitive dun graphe de comparabilit induit un ordre
parfait, on en dduit lalgorithme suivant de coloration minimale des sommets.
Algorithme de coloration minimale des sommets dun graphe de comparabilit
1. Dterminer une orientation transitive de G (par exemple laide de lalgorithme
ci-dessus), et poser i := 1.
2. Tant quil existe encore des sommets colorer faire
donner la couleur i tous les sommets sans prdcesseur,
ter ces sommets du graphe,
poser i := i +1
34 N
o
6 CAHIERS DE LA CRM
Exercice 69
Une compagnie de transport a un ensemble de trajets effectuer. On dcide de reprsenter
ceci par un graphe : un arc de T
i
T
j
indique que le trajet T
j
peut tre effectu par le mme
vhicule que celui qui a effectu le trajet T
i
.
1. De quel type est le graphe obtenu ?
2. Interprtez (dans le graphe non orient) le problme de la recherche dun nombre
minimum de vhicules.
Exemple
Trajet T
1
T
2
T
3
T
4
de A B C B
B C A A
dpart 6h 10h 8h 12h
Dure du trajet A B C
A 1h 3h
B 2h 1h
C 2h 4h
Exercice 70
On a demand un consommateur de comparer n marques de rasoir deux deux, en
indiquant pour chaque paire une prfrence stricte.
1. Est-il vrai que lon peut toujours classer les marques M
1
, M
2
, . . . , M
n
de manire que
lon ait M
1
> M
2
> . . . > M
n
(o M
i
> M
j
indique que M
i
est prfre M
j
) ?
2. On constate que le graphe associ ces prfrences (M
i
>M
j
donne un arc (M
i
, M
j
))
est sans circuit. Que peut-on dire de la marque M
1
(telle que M
1
> . . . > M
n
) ?
Est-il possible davoir deux marques qui ont t prfres au mme nombre dautres
marques ?
3. Existe-t-il toujours une marque M
1
telle que M
1
> M
j
, j = 1 ? Existe-t-il toujours
une marque M
1
telle que pour j = 1 :
soit M
1
> M
j
soit M
k
telle que M
1
> M
k
> M
j
?
2.7 Algorithme de Dijkstra
Edgser Wybe Dijkstra (1930-2002) a propos en 1959 un algorithme qui permet de calculer
le plus court chemin entre un sommet particulier et tous les autres. Le rsultat est une
arborescence, cest--dire un arbre avec un sommet particulier appel racine.
Numrotons les sommets du graphe G = (V, E) de 1 n. Supposons que lon sintresse
aux chemins partant du sommet 1. On construit un vecteur =
_
(1); (2); . . . ; (n)
_
ayant n composantes tel que ( j) soit gal la longueur du plus court chemin allant de 1
au sommet j . On initialise ce vecteur c
1j
, cest--dire la premire ligne de la matrice
des cots du graphe, dnie comme indiqu ci-dessous :
c
i j
=
_

_
0 si i = j
si i = j et (i, j) E
(i, j) si i = j et (i, j) E
o (i, j) > 0 est le poids de larc (i, j).
On construit un autre vecteur p pour mmoriser le chemin pour aller du sommet 1 au
sommet voulu. La valeur p(i) donne le sommet qui prcde i dans le chemin.
CAHIERS DE LA CRM N
o
6 35
On considre ensuite deux ensembles de sommets, S initialis {1} et T initialis
{2, 3, . . . , n}. chaque pas de lalgorithme, on ajoute S un sommet jusqu ce que S =V
de telle sorte que le vecteur donne chaque tape la longueur minimale des chemins de
1 aux sommets de S.
Algorithme de Dijkstra
On suppose que le sommet de dpart (qui sera la racine de larborescence) est le sommet
numrot 1. Notons quon peut toujours renumroter les sommets pour que ce soit le cas.
Initialisations
( j) = c
1j
et p( j) = NIL, pour 1 j n
Pour 2 j n faire
Si c
1j
< alors p( j) = 1.
S = 1 ; T ={2, 3, . . . , n}.
Itrations
Tant que T nest pas vide faire
Choisir i dans T tel que (i) est minimum
Retirer i de T et lajouter S
Pour chaque successeur j de i, avec j dans T , faire
Si ( j) > (i) +(i, j) alors
( j) = (i) +(i, j)
p( j) = i
Exemple
1 5
4
2 3
4
10 5
3 2
15
3
7
Initialisations
S ={1} ; T ={2, 3, 4, 5} ; = (0, 15, , , 4) ; p = (NIL, 1, NIL, NIL, 1)
1re itration
i = 5 car (5) = min(15, , , 4) = 4
S ={1, 5} ; T ={2, 3, 4}
les successeurs de 5 dans T sont 3 et 4
(3) prend la nouvelle valeur min(; (5) +(5; 3)) = min(; 4+7) = 11 ; p(3) = 5
(4) prend la nouvelle valeur min(; (5) +(5; 4)) = 9 ; p(4) = 5
do les nouveaux vecteurs = (0, 15, 11, 9, 4) et p = (NIL, 1, 5, 5, 1)
36 N
o
6 CAHIERS DE LA CRM
2me itration
i = 4 ; (4) = 9
S ={1, 5, 4} ; T ={2, 3}
le seul successeur de 4 dans T est 2
(2) prend la nouvelle valeur min(15; (4) +(4; 2)) = min(15; 9+3) = 12 ; p(2) = 4
do les nouveaux vecteurs = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)
3me itration
i = 3 ; (3) = 11
S ={1, 5, 4, 3} ; T ={2}
le seul successeur de 3 dans T est 2
(2) garde sa valeur car min(12; (3) +(3; 2)) = min(12; 11+3) = 12
do les vecteurs inchangs = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)
4me itration
i = 2 ; (2) = 12
S ={1, 5, 4, 3, 2} ; T ={}
= (0, 12, 11, 9, 4)
p = (NIL, 4, 5, 5, 1)
Lalgorithme se termine, car T ={}.
On peut lire les cots des chemins les plus courts dans et les chemins eux-mmes grce
au vecteur p. Par exemple, le chemin minimal de 1 4 est de cot 9, car (4) =9. Cest le
chemin 154, car p(4) = 5 et p(5) = 1.
Voici la rponse sous forme darborescence :
1 5
4
2 3
4
5
3
7
Exercice 71
Appliquez lalgorithme de Dijkstra au graphe de lexemple ci-dessus pour trouver tous les
plus courts chemins en partant des sommets 2, 3, 4 et 5.
Exercice 72
Expliquez pourquoi des arcs avec des poids ngatifs pourraient poser problme dans la
recherche dun plus court chemin dans un graphe.
2.8 Rseau PERT (Project Evaluation and Review Technique)
Le problme du plus long chemin dans les digraphes sans circuit trouve une application
dans lordonnancement et la planication des tches composant un projet complexe, par
exemple la construction dune maison.
On fait correspondre chaque tche un arc dun digraphe, sa dure dexcution tant gale
au poids de cet arc. Le digraphe rete les prcdences requises dans lexcution du projet.
CAHIERS DE LA CRM N
o
6 37
Ainsi, la tche correspondant larc (i, j) ne peut commencer que si toutes les tches
correspondant des arcs (k, i) ont t compltes. Le digraphe peut contenir des tches
ctives de dure nulle an de forcer certaines prcdences.
Les sommets du digraphe reprsentent des vnements, dbut (n) des activits corres-
pondant aux arcs dont ils sont lextrmit initiale (nale). Le fait que le digraphe est sans
circuit est garant de la faisabilit du projet. En effet, lexistence dun circuit implique-
rait une contradiction dans les prcdences : une tche devant en mme temps prcder et
suivre une autre !
On supposera dornavant que les sommets ont dj t numrots de 1 n de manire
compatible avec leurs rangs, cest--dire que r( j) > r(i) implique j > i (voir lalgorithme
de calcul du rang). En plus, si le digraphe possde plusieurs sommets sans prdcesseur,
on supposera avoir introduit un sommet 1 reli par un arc de dure nulle chacun de ces
sommets. Ce sommet indique le dbut du projet. De mme, si le digraphe possde plusieurs
sommets sans successeur, ceux-ci seront relis par un arc de dure nulle un dernier som-
met n (n du projet). Enn, on supposera limins les arcs parallles par lintroduction de
tches ctives.
Algorithme du chemin critique
Donnes : Digraphe G = (V, E), sans circuit, des activits avec leur dure d
ik
.
Notations :
P(i) ={k V | (k, i) E} : cest lensemble des sommets prdcesseurs de i.
S(i) ={k V | (i, k) E} : cest lensemble des sommets successeurs de i.
Rsultat :

i
: dbut au plus tt des activits correspondant aux arcs (i, k) partant de i,

i
: n au plus tard des activits correspondant aux arcs (k, i) arrivant i,
dure du chemin critique.
Dbut
Calcul des dates de dbut au plus tt (rcurrence en avanant dans le projet)

1
:= 0
Pour k := 2 n faire
k
:= max{
j
+d
jk
| j P(k)}
Calcul des dates de n au plus tard (rcurrence en reculant dans le projet)

n
:=
n
Pour k := n1 1 faire
k
:= min{
j
d
k j
| j S(k)}
Fin.
Dnitions
Un sommet i est critique si
i
=
i
.
Un arc (i, j) est critique si ses extrmits sont des sommets critiques et d
i j
=
j

i
.
Un chemin critique est un chemin de 1 n nutilisant que des arcs critiques, cest--dire
des activits telles que tout retard dans leur excution provoquerait un retard de la n du
projet.
La dure du chemin critique est donne par
n
(ou par
n
, les deux valeurs tant
toujours gales). Elle correspond la dure minimale du projet tant donnes les dures
des tches le composant et les prcdences respectives.
38 N
o
6 CAHIERS DE LA CRM
Exemple
Ci-dessous le graphe des prcdences obtenu avec lalgorithme du chemin critique.
Le chemin critique est en gras.
Tches Prcdences Dure (jours)
A 3
B 9
C 5
D A 8
E B 4
F B 7
G B 20
H C, F 6
I D, E 5
Conventions dcriture :
j
k
Nom de la tche
Dure de la tche

j

j

k

k
3 5
1 2 6
4
A
3
D
8
B
9
E
4
G
20
I
5
C
5
F
7
H
6
3 16 13 24
0 0 9 9 29 29
16 23
Exercice 73
Refaites le graphe des prcdences de lexemple en utilisant lalgorithme du chemin cri-
tique.
Exercice 74
La construction dun entrept est divise en dix tches dont les caractristiques sont don-
nes dans le tableau ci-dessous. Trouvez le chemin critique.
Tches Nature Prcdences Dure (jours)
A Acceptation des plans par le propritaire 4
B Prparation du terrain 2
C Commande des matriaux A 1
D Creusage des fondations A, B 1
E Commande des portes et fentres A 2
F Livraison des matriaux C 2
G Coulage des fondations D, F 2
H Livraison des portes et fentres E 10
I Pose des murs, de la charpente et du toit G 4
J Mise en place des portes et fentres H, I 1
Exercice 75
La rnovation du sjour dun appartement se dcompose en plusieurs tches dcrites dans
le tableau ci-dessous. Ce dernier donne galement les prcdences respecter lors de la
planication des travaux ainsi quune estimation de la dure de chacune des tches.
CAHIERS DE LA CRM N
o
6 39
Tches Prcdences Dure (jours)
A Enlvement des portes 1/2
B Ponage et peinture des portes A 3
C Pose des portes B, J 1/2
D Arrachage des papiers peints 1
E Tirage des ls lectriques D 1
F Pose des prises E, H, I 1/2
G Ragrage des murs E, A 2
H Peinture du plafond G 2
I Pose des papiers peints G 3
J Peinture des cadres H, I 1
K Arrachage de la moquette H, I, J 1/2
L Ponage du parquet K 1
M Imprgnation et schage du parquet L, F 4
N Peinture du balcon 2
O Changement des protections solaires N 1
1. Reprsentez le graphe des prcdences de ces travaux de rnovation.
2. Dterminez une dure totale minimale de rnovation en exhibant un chemin critique
dans ce graphe.
Bibliographie
[1] COGIS O., ROBERT C., Thorie des graphes, Vuibert, 2003
[2] DROESBEKE F., HALLIN M., LEFEVRE C., Les graphes par lexemple, Ellipse, 1987
[3] HERTZ A., Lagrapheur - Intrigues policires saveur mathmatique, Presses inter-
nationales Polytechnique, 2010
[4] GONDRAN M., MINOUX M., Graphes et algorithmes, 4e dition, Lavoisier, 2009
[5] SKIENA S., Implementing Discrete Mathematics : Combinatorics and Graph Theory
With Mathematica, Addison-Wesley, 1990
[6] WEST D., Introduction to Graph Theory, 2nd edition, Prentice Hall, 2001
40 N
o
6 CAHIERS DE LA CRM
Lexique
Acyclique (Acyclic)
Un graphe est acyclique sil ne contient aucun cycle.
Adjacent (Adjacent)
Deux sommets sont adjacents sils sont relis par une arte. On qualie souvent de voisins
deux sommets adjacents.
Arborescence (Rooted tree)
Arbre avec un sommet distingu r (la racine).
Arbre (Tree)
Graphe connexe ne contenant aucun cycle.
Arbre couvrant (Spanning tree)
Un sous-graphe maximum dun graphe qui est aussi un arbre. On parle aussi darbre de
recouvrement.
Arc (Arc)
Une arte oriente dun digraphe.
Arte (Edge)
Une arte relie deux sommets dans un graphe. Nous appelons ces deux sommets les extr-
mits de larte.
Biparti (Bipartite)
Un graphe est biparti si ses sommets peuvent tre diviss en deux ensembles X et Y ,
de sorte que toutes les artes du graphe relient un sommet dans X un sommet dans Y .
Les arbres sont des exemples des graphes bipartis. Si G est biparti, il est habituellement
not par G = (X,Y, E), o E est lensemble des artes.
Boucle (Loop)
Arte ou arc partant dun sommet et allant vers lui-mme. Les boucles ne sont pas autori-
ses dans les graphes et digraphes simples.
Chane (Chain)
Une chane dans un graphe est une suite de sommets relis par des artes. La longueur
dune chane est le nombre dartes utilises, ou, ce qui revient au mme, le nombre de
sommets utiliss moins un. Une chane lmentaire ne peut pas visiter le mme sommet
deux fois. Une chane simple ne peut pas visiter la mme arte deux fois.
Chemin (Path)
Un chemin dans un digraphe est une suite de sommets relis les uns aux autres par des
arcs. La longueur du chemin est le nombre darcs utiliss, ou le nombre de sommets moins
un. Un chemin simple ne peut pas visiter le mme arc plus dune fois. Un chemin ferm a
pour dernier sommet le premier.
Circuit (Circuit)
Dans un digraphe, un circuit est un chemin ferm simple.
Clique (Clique)
Sous-graphe complet dun graphe G. Lordre de la plus grande clique de G est not (G).
Prononcer omga de G .
CAHIERS DE LA CRM N
o
6 41
Complet (Complete)
Dans un graphe complet, toutes les paires de sommets sont adjacentes. Un graphe complet
n sommets est not K
n
(le K est en lhonneur de Kuratowski, un pionnier de la thorie
des graphes).
Composante connexe (Connected component)
Dans un graphe, une composante connexe est un sous-graphe induit maximal connexe.
Maximal signie quil ny a pas de sous-graphe induit connexe plus grand contenant les
sommets de la composante.
Connexe (Connected)
Un graphe connexe est un graphe dans lequel chaque paire de sommets est relie par une
chane. Un graphe qui nest pas connexe est dit non connexe, et se dcompose en compo-
santes connexes.
Couplage ou appariement (Matching)
Un couplage est un ensemble dartes tel que chaque sommet du graphe appartient au
plus une arte de cet ensemble.
Couplage parfait (Perfect matching)
Dans un graphe 2n sommets, un couplage avec n artes est dit parfait. Chaque sommet
du graphe est satur par un couplage parfait.
Corde (Chord)
Arte reliant deux sommets non adjacents dun cycle.
Cycle (Cycle)
Dans un graphe, un cycle est une chane simple dont les extrmits concident. On ne
rencontre pas deux fois le mme sommet, sauf celui choisi comme sommet de dpart et
darrive.
Degr (Degree)
Le degr dun sommet est la taille de son voisinage. Le degr dun graphe est le degr
maximum de tous ses sommets.
Diamtre (Diameter)
Le diamtre dun graphe est la plus longue des distances entre deux sommets de ce graphe.
Digraphe (Digraph)
Un digraphe est un graphe dans lequel les artes sont orientes et appeles arcs. Plus for-
mellement, un digraphe est un ensemble de sommets ainsi quun ensemble de paires or-
donnes des sommets, appeles les arcs.
Distance (Distance)
La distance entre deux sommets est la longueur de la plus courte chane entre eux.
Eulrien (Eulerian)
Une chane ou un cycle est dit eulrien si chaque arte du graphe y apparat exactement une
fois. Les chemins et les circuits des digraphes sont dits eulriens sous les mmes condi-
tions.
Feuille (Leaf )
Sommet de degr 1. Aussi appel sommet pendant.
Fort (Forest)
Graphe qui ne contient aucun cycle. Les composantes connexes dune fort sont des arbres.
42 N
o
6 CAHIERS DE LA CRM
Fortement connexe (Strongly Connected)
Dans un digraphe fortement connexe, chaque sommet peut tre atteint depuis nimporte
quel autre par un chemin.
Graphe (Graph)
Un graphe est un ensemble de points, dont certaines paires sont relies par des lignes.
Les points sont appels sommets et les lignes sont nommes artes.
Plus formellement, un graphe est compos de deux ensembles, lensemble des artes (E)
et lensemble des sommets (V ). Lensemble des sommets est simplement une collection
dtiquettes qui permettent de distinguer un sommet dun autre. Lensemble des artes est
constitu de paires non ordonnes dtiquettes de sommets.
Hamiltonien (Hamiltonian)
Une chane ou un cycle est dit hamiltonien si chaque sommet du graphe y apparat exac-
tement une fois. Les chemins et les circuits des digraphes sont dits hamiltoniens sous les
mmes conditions.
Homomorphe (Homeomorphic)
Deux graphes sont homomorphes sils peuvent tous les deux tre obtenus partir dun
graphe commun en remplaant les artes par des chanes simples.
Les deux graphes ci-dessous sont homomorphes.
Ils ont tous les deux t obtenus partir du graphe ci-dessous :
Incident (Incident)
Un sommet est incident une arte sil est situ une des deux extrmits de cette arte.
Inversement, une arte est incidente un sommet si elle touche ce sommet.
Indice chromatique (Chromatic index)
Lindice chromatique dun graphe est le plus petit nombre k pour lequel il existe une k-
coloration des artes. Lindice chromatique du graphe G est not par (G). Prononcer
khi de G .
k-colorable (k-colorable)
Un graphe est dit k-colorable si chacun de ses sommets peut tre assigne une parmi k
couleurs de sorte qu deux sommets adjacents soit assigne une couleur diffrente. Cette
assignation est appele coloration.
Liste dadjacences (Adjacency Structure)
Une reprsentation dun graphe ou dun digraphe qui numre, pour chaque sommet, tous
les sommets qui sont adjacents au sommet donn.
Liste darcs (Arc List)
Une reprsentation dun digraphe utilisant les arcs du digraphe. Ce peut tre une liste de
paires ordonnes de sommets, ou deux listes tries avec le sommet de dpart dans une liste
et le sommet de n la position correspondante de la deuxime liste.
CAHIERS DE LA CRM N
o
6 43
Matrice dadjacences (Adjacency Matrix)
Une matrice carre contenant des 0 et des 1, dont les lignes et les colonnes sont classes
par sommets. Un 1 en position (i, j) signie quil y a une arte (ou arc) du sommet i au
sommet j . Un 0 indique quil ny a aucune arte ou arc. Une matrice dadjacences peut
tre utilise pour des graphes et des digraphes.
Multigraphe (Multigraph)
Un multigraphe est un graphe contenant des boucles et/ou plusieurs artes reliant les
mmes sommets.
Nombre chromatique (Chromatic number)
Le nombre chromatique dun graphe est le plus petit nombre k pour lequel il existe une k-
coloration des sommets. Le nombre chromatique du graphe G est not par (G). Prononcer
gamma de G .
Nombre cyclomatique (Cyclomatic number)
(G) = mn+ p, avec :
n : nombre de sommets
m : nombre darcs
p : nombre de composantes connexes
Ordre (Order)
Lordre dun graphe est le nombre de ses sommets.
Orientation (Orientation)
Une assignation de direction aux artes dun graphe. Une arte oriente est un arc. Le graphe
auquel on a donn une orientation est dit graphe orient ou digraphe.
Partiel (Spanning Subgraph)
Le graphe obtenu en enlevant des artes dun graphe G est appel graphe partiel.
Pendant (Pendant)
Un sommet est pendant sil est de degr 1. Aussi appel feuille si le graphe est un arbre.
Planaire (Planar)
Un graphe planaire est un graphe que lon peut dessiner sur une surface plate sans que ses
artes se croisent. Les graphes que lon ne peut pas dessiner sans croisement sont dits non
planaires.
Racine (Root)
Sommet distingu dun arbre. En distinguant un sommet dun arbre, on obtient une arbo-
rescence.
Rang (Level)
Dans une arborescence, les sommets la mme distance de la racine sont dits tre au mme
rang. La racine est par convention au rang 0 et la hauteur de larbre est le rang maximum.
Rgulier (Regular)
Dans un graphe rgulier, tous les sommets ont le mme degr. Si le degr commun est k,
alors on dit que le graphe est k-rgulier.
Semi-eulrien (semi-eulerian)
Un graphe est semi-eulrien sil est possible de trouver une chane passant une et une seule
fois par toutes les artes, et sil nest pas eulrien.
44 N
o
6 CAHIERS DE LA CRM
Semi-hamiltonien (semi-hamiltonian)
Un graphe est semi-hamiltonien sil est possible de trouver une chane passant une et une
seule fois par tous les sommets, et sil nest pas hamiltonien.
Simple (simple)
Un graphe est dit simple, sil ne contient pas de boucle et sil ny a pas plus dune arte
reliant deux mmes sommets.
Simplicial (simplicial)
Un sommet v est dit simplicial si son voisinage N(v) est une clique.
Sommet (Vertex, pluriel Vertices)
Extrmit dune arte ou dun arc.
Sous-graphe (Induced Subgraph)
Un sous-graphe est obtenu en enlevant un graphe des sommets et toutes les artes inci-
dentes ces sommets.
Stable (Stable)
Un stable dun graphe G est un sous-graphe de G sans arte. Lordre du plus grand stable
de G est not (G) et sappelle nombre de stabilit. Prononcer alpha de G .
Taille (Size)
La taille dun graphe est le nombre de ses artes.
Tournoi (Tournament)
Digraphe complet.
Triangul (Chordal)
Un graphe est triangul si tous ses cycles de longueur suprieur 3 contiennent au moins
une corde.
Voisinage (Neighborhood)
Le voisinage dun sommet est lensemble de tous ses sommets adjacents.
CAHIERS DE LA CRM N
o
6 45
Index
arte, 3
arborescence, 35
arbre, 17
couvrant, 19
maximal, 19
arc, 29
carte, 14
chane, 8
lmentaire, 9
alterne, 13
alterne augmentante, 13
eulrienne, 10
ferme, 9
hamiltonienne, 11
simple, 9
chemin, 29
circuit, 30
clique, 7
composantes connexes, 4
corde, 26
couplage, 13
maximum, 13
parfait, 13
cycle, 9
eulrien, 10
hamiltonien, 11
degr, 7
dun graphe, 8
dun sommet, 7
dune rgion, 15
diamtre, 9
digraphe, 29
fortement connexe, 31
distance, 9, 29
feuille, 17
fort, 17
graphe, 3
biparti, 4
complet, 4
connexe, 4
dintervalles, 5
de comparabilit, 34
eulrien, 10
hamiltonien, 11
orient, 29
parfait, 24
partiel, 6, 19
planaire, 3, 14
planaire topologique, 14
rgulier, 8
semi-eulrien, 10
semi-hamiltonien, 11
simple, 3
triangul, 26
indice chromatique, 25
listes dadjacences, 16
matrice dadjacences, 15
multigraphe, 3
nombre chromatique, 21
nombre de stabilit, 21
racine, 35
rang, 33
roi, 30
sparateur, 26
schma dlimination parfait, 28
sommet, 3
pendant, 17
satur, 13
simplicial, 26
sous-graphe, 6
stable, 21
tournoi, 30
46
Ouvrages publis par la Commission Romande
de Mathmatique
OUVRAGES COLLECTIFS DE LA CRM
N
o
18 Gomtrie 2
N
o
21 Mthodes numriques (M.-Y. BACHMANN, H. CATTIN,
P. PINEY, F. HAEBERLI et G. JENNY)
N
o
23 Gomtrie vectorielle et analytique plane
N
o
24 Gomtrie vectorielle et analytique de lespace
N
o
25 Analyse
N
o
26 Probabilits
N
o
27 Notions lmentaires
N
o
28 Algbre linaire
CAHIERS DE LA CRM
N
o
1 Suites de nombres rels Alex WILLA
N
o
2 Cryptologie Nicolas MARTIGNONI
N
o
3 quations algbriques et nombres complexes Martin CUNOD
N
o
4 Sries numriques et sries de Taylor Alex WILLA
N
o
5 Arrt sur image Daniel PONCET-MONTANGE
N
o
6 Introduction la thorie des graphes Didier MLLER
CRM, CRP ET CRC
Formulaires et Tables (Mathmatique, Physique, Chimie)
S. PAHUD
Gomtrie exprimentale I, II et III (Livre de llve)
Gomtrie exprimentale I, II et III (Notes mthodologiques insrer)
Site web de la CRM
http://www.sspmp.ch/crm/
Diffusion : Pahud & Cie
http://www.diffusionpahud.ch/
c 2012 CRM Toute reproduction dun extrait de ce livre par
quelque procd que ce soit, notamment par
photocopie ou numrisation, est interdite.
Cahiers de la CRM dj parus
CAHIERS DE LA CRM
Suites de
nombres rels
Alex Willa
CAHIER NO 1 COMMISSION ROMANDE DE MATHMATIQUES
CAHIERS DE LA CRM
Cryptologie
Nicolas Martignoni
CAHIER NO 2 COMMISSION ROMANDE DE MATHMATIQUES
CAHIERS DE LA CRM
quations algbriques
et nombres complexes
Une approche historique
Martin Cunod
CAHIER NO 3 COMMISSION ROMANDE DE MATHMATIQUE
CAHIERS DE LA CRM
Sries numriques
et sries de Taylor
Alex Willa
CAHIER NO 4 COMMISSION ROMANDE DE MATHMATIQUE
N
o
1 : Suites de
nombres rels
N
o
2 : Cryptologie N
o
3 : quations &
nombres complexes
N
o
4 : Sries
numriques
CAHIERS DE LA CRM
Arrt sur image
avec Mathematica
Daniel Poncet-Montange
CAHIER NO 5 COMMISSION ROMANDE DE MATHMATIQUE
CAHIERS DE LA CRM
Introduction la
thorie des graphes
Didier Mller
CAHIER NO 6 COMMISSION ROMANDE DE MATHMATIQUE
N
o
5 : Arrt sur image N
o
6 : Thorie des
graphes
Commission Romande de Mathmatique