Théorie des Graphes et Optimisation

Partie I

1
 Présentation du cours : Partie I
Pré-requis : --.
 Objectifs : Permet à l’étudiant d’acquérir les connaissances de base sur la
théorie de graphe, leur permettant par la suite de comprendre les structures
topologiques des réseaux informatiques et d’appliquer des algorithmes de
recherche et d’optimisation.
Contenu :
Graphe non orienté
Quelques types de graphes
Graphe partiel et sous-graphe
Chaînes et cycles
Graphes Eulériens
Graphes Hamiltoniens
Représentations non graphiques d’un graphe
Coloration
Graphes orientés
Couplages
Graphes planaires
Recherche d’un parcours dans un graphe
 Plan
Introduction
1.1. Représentation graphique
 2. Quelques types de graphes
 3. Graphe partiel et sous-graphe
 4. Degrés
 5. Chaînes et cycles
 6. Graphes eulériens
 7. Graphes Hamiltoniens
 8. Représentations non graphiques d’un graphe
 9. Couplages
 10. Graphes planaires
 11. Coloration
 12. Recherche d’un parcours dans un graphe
Démonstrations des théorèmes
Références
Un bref historique de la théorie des graphes :
Tout le monde s’accorde à considérer que la théorie des graphes est née en 1736 avec
la communication d’Euler (1707-1783) dans laquelle il proposait une solution au célèbre
problème des ponts Königsberg . Le problème posé était le suivant :
Deux iles A et D sur la rivière Pregel à Königsberg (aujourd’hui Kaliningrad) étaient
reliées entre elles ainsi qu’aux rivages B et C à l’aide de sept ponts. Le problème
consistait, à partir d’une terre quelconque A, B, C ou D, à traverser chacun des ponts une
fois et une seule et à revenir à son point de départ,

C
c b a

A d
e D
f
B g
 Solution :
Euler représente cette situation à l’aide d’un « dessin » où les sommets
représentent les terres et les arêtes représentent les ponts, comme montre
la figure 2

A D

B
 Solution :
Euler représente cette situation à l’aide d’un « dessin » où les sommets
représentent les terres et les arêtes représentent les ponts, comme montre
la figure 2

A D

Il est possible de résoudre le problème si tous les sommets du graphe

sont de degré pair.
Or, ce n’est pas le cas de notre graphe, donc ce n’est pas possible
Introduction
Les graphes permettent de manipuler plus facilement des objets et leurs
relations avec une représentation graphique naturelle.

L’ensemble des techniques et outils mathématiques mis au point en

théorie des graphes permet de démontrer facilement des propriétés,
d’en déduire des méthodes de résolution, des algorithmes,….
Par exemple :
 Quel est le plus court chemin (en distance ou en temps) pour se rendre
d’une ville à une autre ?
 Peut-on mettre une rue en sens unique sans rendre impossible la
circulation en ville ?
 Comment organiser un horaire d’occupation ?
 …

Un graphe permet de décrire un ensemble d’objets et leurs relations,

c'est-à-dire les liens entre les objets.
Définition d’un graphe (non orienté)

Un graphe fini G = (V,E) est défini par :

 l’ensemble fini V = {v1, v2, . . . , vn} dont les éléments sont appelés
sommets (Vertices en anglais),
 l’ensemble fini E = {e1, e2, . . . , em} dont les éléments sont appelés arêtes
(Edges en anglais).

 Une arête e de l’ensemble E est définie par une paire non ordonnée de
sommets, appelés les extrémités de e.
 Si l’arête e relie les sommets a et b, on dira que ces sommets sont adjacents,
ou incidents avec e, ou bien que l’arête e est incidente avec les sommets a et
b.
 On appelle ordre d’un graphe le nombre de sommets n de ce graphe
 Représentation graphique

 Les graphes tirent leur nom du fait qu’on peut les représenter par des dessins.
 À chaque sommet de G, on fait correspondre un point distinct du plan et on
relie les points correspondant aux extrémités de chaque arête.
 Il existe donc une infinité de représentations d’un graphe. Les arêtes ne sont
pas forcément rectilignes.
 Si on peut dessiner un graphe G dans le plan sans aucune arête ne coupe une
autre (les arêtes ne sont pas forcément rectilignes), on dit que G est planaire.
 Le graphe G ci-dessous est planaire.
 Représentation graphique

 Les graphes tirent leur nom du fait qu’on peut les représenter par des dessins.
 À chaque sommet de G, on fait correspondre un point distinct du plan et on
relie les points correspondant aux extrémités de chaque arête.
 Il existe donc une infinité de représentations d’un graphe. Les arêtes ne sont
pas forcément rectilignes.
 Si on peut dessiner un graphe G dans le plan sans aucune arête ne coupe une
autre (les arêtes ne sont pas forcément rectilignes), on dit que G est planaire.
 Le graphe G ci-dessous est planaire.
Degrés
Définition : Degré d’un sommet :
On appelle degré du sommet v, et on note d(v), le nombre d’arêtes incidentes à
ce sommet.

Définition :
• Une boucle est une arête qui relie un sommet à lui-même.
• Un graphe est dit simple, s’il ne contient pas de boucles et s’il n’y a pas plus
d’une arête reliant deux mêmes sommets.

Attention ! Une boucle sur un sommet compte double.

Exemple :
Dans le multigraphe ci-contre, on a les degrés :
Degrés
Définition : Degré d’un sommet :
On appelle degré du sommet v, et on note d(v), le nombre d’arêtes incidentes à
ce sommet.

Définition :
• Une boucle est une arête qui relie un sommet à lui-même.
• Un graphe est dit simple, s’il ne contient pas de boucles et s’il n’y a pas plus
d’une arête reliant deux mêmes sommets.

Attention ! Une boucle sur un sommet compte double.

Exemple :
Dans le multigraphe ci-contre, on a les degrés :
d(v1) = 2
d(v2) = 2
d(v3) = 4
d(v4) = 1
d(v5) = 3
Définition :Graphe simple et Multi graphe :

 Un graphe est simple si au plus une arête relie deux sommets et s’il n’y a
pas de boucle sur un sommet.

 On peut imaginer des graphes avec une arête qui relie un sommet à lui-
même (une boucle), ou plusieurs arêtes reliant les deux mêmes sommets.
On appellera ces graphes des multi graphes.
Théorème 1 (Lemme des poignées de mains)
La somme des degrés des sommets d’un graphe simple est égale à deux fois le
nombre d’arêtes.

Preuve : soit G = (V,E) un graphe simple. Quand on calcule la somme

des degrés des sommets, chaque arête (x, y) de E est comptée deux fois,
une première fois pour d(x) et une seconde fois pour d(y). Donc, cette
somme est finalement égale à deux fois le nombre d’arêtes.

Exercice :
Exercice 1
 On a six wagons à trier. Dans la gare de triage, les wagons entrent dans
l’ordre 2, 5, 3, 6,1, 4 et doivent sortir dans l’ordre croissant. Deux
wagons i et j peuvent être mis sur la même voie si et seulement s’ils
entrent dans l’ordre dans lequel ils doivent sortir.
 Dessinez un graphe illustrant la situation, en indiquant ce que
représentent les sommets et les arêtes de votre graphe. Quel sera le
nombre minimal de voies nécessaires au tri ?

Solution
On représente les wagons par les sommets. Une
arête relie deux sommets i et j si les wagons i et j
ne peuvent pas être sur la même voie. On obtient le
graphe ci-contre.
On voit que 1, 3 et 5 ne peuvent pas être sur la
même voie.
Il faut donc trois voies au minimum.
Exercice 2:
Une suite décroissante (au sens large) d’entiers est graphique s’il existe
un graphe simple dont les degrés des sommets correspondent à cette
suite. Par exemple, un triangle correspond à 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).
Solution
Les suites (3, 3, 2, 1, 1), (3, 3, 2, 2) et (4, 2, 1, 1, 1, 1) sont graphiques, comme le
montrent les graphes ci-dessous :

Les graphes distincts ci-dessous correspondent tous deux à la suite (3, 2, 2, 2, 1) :

 Chaînes et cycles
Définitions :
 chaîne dans G, est une suite ayant pour éléments alternativement des sommets et des
arêtes, commençant et se terminant par un sommet, et telle que chaque arête est
encadrée par ses extrémités.

 On dira que la chaîne relie le premier sommet de la suite au dernier sommet. En plus,
on dira que la chaîne a pour longueur le nombre d’arêtes de la chaîne.

 Le graphe ci-dessous contient entre autres les chaînes (v1, e1, v2, e2, v3, e5, v5) et
(v4, e4, v3, e2, v2, e1, v1).

On ne change pas une chaîne en inversant l’ordre des

éléments dans la suite correspondante.
Ainsi, les chaînes (v1, e3, v3, e4, v4) et (v4, e4, v3, e3, v1)
sont identiques.
 Chaînes et cycles

Définition : Degré d’un graphe :

 Le degré d’un graphe est le degré maximum de tous ses sommets.

Dans l’exemple ci-dessous, le degré du graphe est 4, à cause du

sommet v3 .

Définition : Un graphe dont tous les sommets ont le même degré est dit
régulier. Si le degré commun est k, alors on dit que le graphe est k-régulier.
Chaînes et cycles

Définition :
 On appelle distance entre deux sommets la longueur de la plus courte chaîne les
reliant.
 On appelle diamètre d’un graphe la plus longue des distances entre deux sommets.
Chaînes et cycles

Définition :
 On appelle distance entre deux sommets la longueur de la plus courte chaîne les
reliant.
 On appelle diamètre d’un graphe la plus longue des distances entre deux sommets.

Remarque :
 Le diamètre d’un graphe complet est égal à 1 car
tous les sommets sont reliés entre eux par au moins
une arête.
 Le diamètre d’un graphe qui n’est pas connexe est
infini car il y a des sommets qui ne sont reliés par
aucune chaîne.
La distance de ces sommets est donc infinie.
 Chaînes et cycles
Définition :
Une chaîne est élémentaire si chaque sommet y apparaît au plus une fois.

Une chaîne est simple si chaque arête apparaît au plus une fois.
Dans le graphe précédent, (v1, e1, v2, e2, v3) est une chaîne simple et
élémentaire.

Une chaîne dont les sommets de départ et de fin sont les mêmes est appelée
chaîne fermée.
Dans le graphe précédent, (v4, e4, v3, e5, v5, e5, v3, e4, v4) est une chaîne
fermée.

Une chaîne fermée simple est appelée cycle si seul le sommet de départ apparaît
deux fois dans la chaîne.
Dans le graphe précédent, la chaîne (v1, e1, v2, e2, v3, e3, v1) est un cycle.
 Connexités :
Définition :
On définit la relation binaire de connexité simple , sur l’ensemble V d’un
graphe G=(V,E) non orienté par :

ou u=w

Propriétés :
• est une relation d’équivalence,
• Les classes d’équivalences produites sur V par sont appelées les
composantes simplement connexes du graphe G.
• Le nombre de classe d’équivalence distinctes correspondant à est appelé
le nombre de connexité simple du graphe,
Connexités :
Définition :
Un graphe est dit simplement connexe si le nombre de connexité simple est
égal à 1.

Remarque :
Un graphe est simplement connexe s’il existe une chaine reliant une paire
de sommets quelconques.

Un graphe est connexe s’il est possible, à partir de n’importe quel sommet,
de rejoindre tous les autres sommets en suivant les arêtes.

Exemple : Graphe connexe

Graphe non connexe :

 Un graphe non connexe se décompose en des composantes connexes.

 Sur le graphe ci-dessous, les composantes connexes sont {1,2,3,4} et
{5,6}.
Graphe non connexe
 V = {1,2,3,4,5,6}
 E = {1,3},{1,4},{2,3},{3,4},{5,6}
Graphe complet :
 Un graphe est complet si chaque sommet du graphe est relié directement à
tous les autres sommets.
Graphe complet
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}
Graphe biparti :
Définition :
 Un graphe est biparti si ses sommets peuvent être divisés en deux ensembles X et Y ,
de sorte que toutes les arêtes du graphe relient un sommet dans X à un sommet dans
Y.
 Les éléments de X ne sont reliés entre eux par aucune arête.
 Les éléments de Y ne sont reliés entre eux par aucune arête.

Dans l’exemple ci-dessous, on a X = {1,3,5} et Y = {2,4}, ou vice versa.

Graphe biparti :
V = {1,2,3,4,5}
E ={1,2},{1,4},{2,5},{3,4},{4,5}
 Graphe biparti :
Théorème 2
Un graphe est biparti si et seulement s’il ne contient aucun cycle de longueur
impaire.
Exercice : Montrez que ce graphe est biparti :

Solution
C’est un graphe biparti.
X={1,4,5,8}
Y={2,3,6,7 }
Graphe partiel et sous-graphe

Définition :
 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 arêtes 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
l’ensemble des sommets est A et l’ensemble des arêtes E(A) est
formé de toutes les arêtes de G ayant leurs deux extrémités dans
A.

 Autrement dit, on obtient G’ en enlevant un ou plusieurs sommets

au graphe G, ainsi que toutes les arêtes incidentes à ces sommets.
Graphe partiel et sous-graphe :

Un graphe partiel d’un 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.
Graphe stable

Définition :
 Un stable, appelé aussi ensemble indépendant, est un ensemble de
sommets deux à deux non adjacents.
 La taille d’un stable est égale au nombre de sommets qu’il contient.
 Un ensemble stable maximum est un ensemble stable de cardinalité
maximum.
 Le nombre de stabilité d’un graphe noté α(G) est la cardinalité d’un
stable maximum.
 Graphes eulériens

Définition :
 On appelle chaîne eulérienne d’un graphe G une chaîne passant une et une
seule fois par chacune des arêtes de G. Un graphe ne possédant que des
chaînes eulériennes est semi-eulérien.

 On appelle cycle eulérien d’un graphe G un cycle passant une et une seule
fois par chacune des arêtes de G. Un graphe est dit eulérien s’il possède un
cycle eulérien.

 Plus simplement, on peut dire qu’un graphe est eulérien (ou semi-eulérien)
s’il est possible de dessiner le graphe sans lever le crayon et sans passer
deux fois sur la même arête.
Remarque : L’adjectif « Eulérien » vient du nom du grand mathématicien
Leonhard Euler,
 Graphes eulériens
Théorème d’Euler :
Un graphe simple admet une chaîne eulérienne entre deux sommets a et b si
et seulement si ce graphe est connexe et si a et b sont les seuls sommets de
degré impair de ce graphe.
Les chaînes eulériennes du graphe auront alors ces deux sommets pour
extrémités.

Théorème d’Euler :
 Un graphe simple admet un cycle eulérien si et seulement si ce graphe est
connexe et s’il n’a aucun sommet de degré impair.

Corollaire d’Euler :
Un graphe ayant plus de deux sommets de degré impair ne possède pas de
chaîne eulérienne.
Graphes eulériens
Exercice :
un des problèmes fondateurs de la théorie des graphes, proposé par le
mathématicien suisse Leonhard Euler en 1736.
En 1652, la ville de Königsberg (aujourd’hui Kaliningrad) possède sept ponts
enjambant la Pregel, qui coule de part et d’autre de l’île de Kneiphof.
 Au cours d’une promenade, est-il possible de passer sur tous les ponts de la
ville une et une seule fois ?

Solution
Non, il n’est ni eulériens ni
semi eulériens
Graphes eulériens

Exercice :
Les graphes suivants sont-ils eulériens (ou semi-eulériens) ?

Solution
Le graphe de gauche n’est évidemment pas eulérien puisque non connexe. Celui
du milieu est eulérien car tous les sommets sont de degré pair. Celui de droite est
semi-eulérien, car seuls deux sommets sont de degré impair.
Graphes eulériens
Exercice :
Est-il possible de tracer une courbe, sans lever le crayon, qui coupe
chacun des 16 segments de la figure suivante exactement une fois ?

Solution
Non, car le graphe correspondant n’est pas eulérien. Pour construire ce graphe,
on a représenté les régions délimitées par des cloisons par les sommets ; les
sommets x et y sont reliés si les régions x et y sont séparées par une cloison.
Chaque cloison correspond donc à une arête du graphe.
 Graphes Hamiltoniens

Définition :
 Dans un graphe non orienté, une chaîne est appelée « chaîne hamiltonienne » si
et seulement si c’est une chaîne qui passe une fois et une seule par chaque
sommet du graphe.

 Un graphe ne possédant que des chaînes hamiltoniennes est semi-hamiltonien.

 On appelle cycle hamiltonien d’un graphe G un cycle passant une et une seule
fois par chacun des sommets de G.

 Un graphe est dit hamiltonien s’il possède un cycle hamiltonien.

Graphes Hamiltoniens

Contrairement aux graphes eulériens, il n’existe pas de caractérisation simple

des graphes (semi-)hamiltoniens. On peut énoncer quelques propriétés et
conditions suffisantes :

Théorème 4 (Ore) :
Soit G un graphe simple d’ordre n ≥ 3. Pour toute paire {x, y} de sommets non
adjacents,
Si d(x)+d(y) ≥ n, alors G est hamiltonien.

Corollaire 1 (Dirac) :
Soit G un graphe simple d’ordre n ≥ 3. Si pour tout sommet x de G,
on a d(x) ≥ n/2 , alors G est hamiltonien.
Graphes Hamiltoniens
Remarques :
– Un graphe possédant un sommet de degré 1 ne peut pas être hamiltonien ;

– Si un sommet dans un graphe est de degré 2, alors les deux arêtes incidentes
à ce sommet doivent faire partie du cycle hamiltonien ;

– es graphes complets Kn sont hamiltoniens

Graphes Hamiltoniens :

Exercice :
Dessinez un graphe d’ordre au moins 5 qui est. . .
1) hamiltonien et eulérien
2) hamiltonien et non eulérien
3) non hamiltonien et eulérien
4) non hamiltonien et non eulérien.
 Démonstrations des théorèmes

Théorème 1 (Lemme des poignées de mains)

La somme des degrés des sommets d’un graphe est égale à deux fois le nombre
d’arêtes.

Soit G = (V,E) un graphe simple. Quand on calcule la somme des degrés des
sommets, chaque arête (x, y) de E est comptée deux fois, une première fois pour
d(x) et une seconde fois pour d(y). Donc, cette somme est finalement égale à deux
fois le nombre d’arêtes.
Démonstrations des théorèmes
Théorème 2
Un graphe est biparti si et seulement s’il ne contient aucun cycle de longueur
impaire.
Soit G = (V,E) un graphe. On appellera coloriage d’un graphe G à k couleurs
toute application f de V dans {1, ... , k}. On dira qu’un coloriage f est propre si
deux sommets voisins n’ont pas la même couleur.
Soit G un graphe biparti et f un coloriage à 2 couleurs de G. Si (x0, ..., xn) est
une chaîne, on a pour i 2 {0, ...,n−1}, f (xi) 6= f (xi+1), d’où f (x2k) = f (x0) et f
(x2k+1) = f (x1).
Maintenant, si cette chaîne est un cycle, on a x0 = xn , d’où f (x0) =f (xn), ce
qui implique que n est pair. G ne possède donc pas de cycle de longueur
impaire.
Soit maintenant G = (V,E) un graphe ne possédant pas de cycle de longueur
impaire. On doit construire un coloriage propre de G. Comme les composantes
connexes ne communiquent pas entre elles, on peut se ramener au cas où G est
connexe : il suffira ensuite de recoller les applications.
Soit x0 un sommet quelconque de V . Pour x 2 V , on note l(x) la longueur
minimale
d’un chemin reliant x0 à x. On pose alors f (x) = 1 si l(x) est pair, f (x) = 2
sinon. Soit {x, y} 2 E : il est facile de voir que |l(x)−l(y)| 1. Si on avait l(x) =
l(y), on pourrait
construire un cycle de longueur 2l(x)+1 contenant le point x0 et l’arête {x, y}.
Démonstrations des théorèmes
Théorème 3
Un graphe est eulérien s’il est connexe et si tous ses sommets sont de degré
pair. Il est semi-eulérien si tous ses sommets sauf deux sont de degré pair ; les
chaînes eulériennes du graphe auront alors ces deux sommets pour extrémités.

Supposons que G est eulérien. Dessinons G et effaçons les arêtes que nous
avons déjà parcourues. Chaque passage en un point intermédiaire efface deux
arêtes (arrivée et départ). Ces points intermédiaires sont donc de degré pair
puisqu'à la fin plus aucune arête n'y aboutit. Soit M le point de départ (et aussi
d'arrivée) : chaque passage intermédiaire a effacé deux arêtes, le premier en
avait effacé une et le dernier en efface une autre. Cela fait au total un nombre
pair d'arêtes pour ce point aussi. Lorsque G est semi-eulérien, le même
raisonnement montre que le premier et le dernier point du tracé sont
exactement les deux seuls points de degré impair.
Démonstrations des théorèmes
Théorème 4 (Ore)
Soit G un graphe simple d’ordre 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 (Dirac)
Soit G un graphe simple d’ordre n ≥ 3. Si pour tout sommet x de G, on a d(x) ≥ n/2 , alors G est hamiltonien.

Raisonnons par l'absurde en supposant qu'un graphe G à n sommets satisfait l'hypothèse de l'énoncé mais
n'est pas hamiltonien. Quitte à rajouter à G d'autres arêtes, on peut supposer que G est ''non hamiltonien
maximal'', id est que le rajout d'une seule arête suffirait à le rendre hamiltonien (remarquons que le rajout
d'éventuelles arêtes augmente d(v)+d(w) de sorte que le nouveau graphe continue à satisfaire l'hypothèse sur
les degrés). Soit vw l'arête qu'il suffirait de rajouter pour rendre G hamiltonien.
Désignons v par v1 et w par vn. Introduisant cette hypothétique arête (v nv1), on obtient donc un lacet de
Jordan passant une fois et une seule par chaque sommet de G. Il en résulte que est un chemin de Jordan
``vraiment'' contenu dans G, et donc que G est semi-hamiltonien. Nous allons établir la contradiction en
prouvant que G, non hamiltonien par hypothèse, contient pourtant un lacet de Jordan hamiltonien. Pour cela,
montrons qu'existent, le long du chemin v 1 v2 vn, deux sommets consécutifs vi -1 et vi tels que vi soit relié à v1
et vi -1 à vn. Car alors, le circuit dessiné ci-dessous est bien un lacet de Jordan hamiltonien de G d'où la
contradiction.

Par hypothèse, v1 et vn ne sont pas adjacents, sinon G serait déjà hamiltonien. Il en résulte que d(v 1) + d(vn) n.
Supposons que n'existe aucun couple (vi-1,vi) satisfaisant la propriété ci-dessus, et soit v i1, , vik les sommets
adjacents à vn. Remarquons que i1 2 et ik n -1. Aucun des sommets v1, vi1+1, , vik+1 ne peut alors être adjacent à
v1. Il en résulte que soit qui contredit l'hypothèse. Ceci termine la démonstration.
Exercice 6
Montrez qu’un graphe simple a un nombre pair de sommets de degré
impair.

Solution
Notons P l’ensemble des sommets de degré pair et I l’ensemble des
sommets de degré impair d’un graphe simple G = (V,E). P et I forment
une partition de V . D’après le lemme des poignées de mains, on a :

Or 2· |E| et sont des entiers pairs. est également

pair, puisque c’est la différence de deux entiers pairs. Or,
chaque terme de la somme est impair. Elle ne peut donc
être paire que si le nombre de termes est pair. On a ainsi
montré que le cardinal de I est un entier pair.
Exercice 2 :

 Trois professeurs P1 , P2 , P3 devront donner lundi prochain un

certain nombre d’heures de cours à trois classes C1 , C2 , C3 :
 P1 doit donner 2 heures de cours à C1 et 1 heure à C2 ;
 P2 doit donner 1 heure de cours à C1 , 1 heure à C2 et 1 heure à
C3 ;
 P3 doit donner 1 heure de cours à C1 , 1 heure à C2 et 2 heures à
C3 .
1) Comment représenter cette situation par un graphe ?
2) Quel type de graphe obtenez-vous ?
3) Combien faudra-t-il de plages horaires au minimum?
4) Aidez-vous du graphe pour proposer un horaire du lundi pour
ces professeurs.
Solution
 On obtient le graphe biparti suivant (à gauche) :

En colorant les arêtes de

ce graphe (1 couleur = 1
heure de l’horaire), en
prenant garde que chaque
sommet n’ait pas deux
arêtes incidentes de même
couleur, on obtient le
résultat de droite.

De ce graphe coloré, on tire l’horaire suivant :

Exercice 3
Un tournoi d’échecs oppose 6 personnes. Chaque
joueur doit affronter tous les autres.
1) Construisez un graphe représentant toutes les
parties possibles.
2) Quel type de graphe obtenez-vous ?
3) Si chaque joueur ne joue qu’un match par jour,
combien de jours faudra-t-il pour terminer le tournoi
?
4) Aidez-vous du graphe pour proposer un calendrier
des matches.
Solution
On obtient le graphe complet K6 .

Il faudra 5 jours de tournoi. Voici un calendrier possible :

Ce calendrier a été construit d’après les cinq schémas ci-dessus :

Exercice 4
 Sur un échiquier 3×3, les deux cavaliers noirs sont
placés sur les cases a1et c1, les deux cavaliers blancs
occupant les cases a3 et c3.
 Aidez-vous d’un graphe pour déterminer les
mouvements alternés des blancs et des noirs qui
permettront aux cavaliers blancs de prendre les places
des cavaliers noirs, et vice versa.
 Les blancs commencent.
Solution
 On utilise le graphe qui indique les cases atteignables depuis une case
courante.

Les mouvements sont donc (par exemple) : c3-b1, a3-c2, a1-b3, c1-a2, b1-a3,
c2-a1, b3-c1, a2-c3, c3-b1, a3-c2, a1-b3, c1-a2, b1-a3, c2-a1, b3-c1, a2-c3
Exercice 7
Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit relié
avec exactement trois autres ?

Solution
Considérons le graphe simple dont les sommets représentent les 15 ordinateurs ;
les arêtes représentent les liaisons entre ces ordinateurs. Si chaque appareil est
relié à exactement 3 ordinateurs du réseau, les sommets du graphe sont tous de
degré impair. D’après le résultat établi dans l’exercice 6, un tel graphe doit
posséder un nombre pair de sommets, le réseau est donc impossible.
Exercice 8
On s’intéresse aux graphes 3-réguliers. Construisez de tels graphes
ayant 4, 5, 6 sommets. Qu’en déduisez-vous ? Prouvez-le !

La figure ci-dessus montre deux graphes 3-réguliers (on dit aussi cubiques), ayant
respectivement 4 et 6 sommets. En effet, on constate aisément qu’il n’existe pas
de graphes cubiques ayant un nombre impair de sommets : le nombre d’arêtes
d’un graphe cubique à n sommets est 3n/2 , qui n’est entier que lorsque n est
impair.
 Références
 COGIS O., ROBERT C., Théorie des graphes, Vuibert, 2003.

 DROESBEKE F., HALLIN M., LEFEVRE C., Les graphes par l’exemple, Ellipse,
1987.

 HERTZ A., L’agrapheur - Intrigues policières à saveur mathématique, Presses

internationales Polytechnique, 2010.

 GONDRAN M., MINOUX M., Graphes et algorithmes, 4e édition, Lavoisier, 2009.

 SKIENA S.,Implementing Discrete Mathematics : Combinatorics and Graph Theory

With Mathematica, Addison-Wesley, 1990.

 WEST D., Introduction to Graph Theory, 2nd edition, Prentice Hall, 2001

MULLER D, Introduction à la théorie des graphes, CAHIERS DE LA CRM, 2012