Théorie des graphes Préparation CAPES UCBL

Introduction Contenus Capacités attendues

Vocabulaire élémentaire des
Ces quelques pages ont pour objectif de vous initier aux notions de
graphes :
théorie des graphes enseignées en Terminale ES. Le programme de
sommets, sommets adjacents, Les termes seront introduits
Terminale (voir ci-après) est construit sur la résolution de problèmes.
arêtes, degré d’un sommet, ordre à l’occasion de résolutions
Aucune théorie formelle n’est introduite, mais beaucoup de vocabu-
d’un graphe, chaı̂ne, longueur de problèmes et ne feront
laire. Il faut donc connaı̂tre quelques définitions pour pouvoir affronter
d’une chaı̂ne, graphe complet, pas l’objet d’une définition
sans mal les oraux du CAPES. Une leçon d’exposé est consacrée aux
distance entre deux sommets, dia- formelle, sauf lorsque cette
graphes, et le thème est déjà paru lors de l’épreuve sur dossier.
mètre, sous-graphe stable, graphe dernière définition est simple
connexe, nombre chromatique, et courte (degré d’un som-
Programme de Terminale ES Spécialité chaı̂ne eulérienne, matrice associée met, ordre d’un graphe par
à un graphe, matrice de transition exemple).
Résolution de problèmes à l’aide de graphes pour un graphe pondéré par des
Contenus Capacités attendues probabilités.
Résolution de problèmes conduisant Résultats élémentaires sur les graphes :
à la modélisation d’une situation par – lien entre la somme des degrés des
un graphe orienté ou non, éventuel- Les problèmes proposés met- sommets et le nombre d’arêtes d’un On pourra, dans des cas
lement étiqueté ou pondéré et dont tront en jeu des graphes graphe ; élémentaires, interpréter
la solution est associée : simples, la résolution pouvant – conditions d’existence de chaı̂nes et les termes de la puissance
– au coloriage d’un graphe le plus souvent être faite sans cycles eulériens ; 𝑛-ième de la matrice
– à la recherche du nombre chroma- recours à des algorithmes. – exemples de convergence pour des associée à un graphe.
tique graphes probabilistes à deux som-
– à l’existence d’une chaı̂ne ou d’un On indiquera que pour des mets, pondérés par des probabilités.
cycle eulérien graphes complexes, des algo-
– à la recherche d’une plus courte rithmes de résolutions de cer-
chaı̂ne d’un graphe pondéré ou tains problèmes sont absolu- Références et prérequis
non ment nécessaires.
– à la caractérisation des mots re- Dans tout livre de Terminale ES spécialité, vous trouverez de nom-
connus par un graphe étiqueté et, On présentera un algorithme breux exercices et des méthodes pratiques (Déclic, Hyperbole,. . . ).
réciproquement, à la construction simple de coloriage des N’hésitez pas à les consulter pour vous habituer aux programmes et
d’un graphe étiqueté reconnais- graphes et un algorithme vous préparer à l’épreuve sur dossier.
sant une famille de mots, de recherche de plus courte Peu de notions sont utilisées en théorie des graphes. On utilise prin-
– à la recherche d’un état stable chaı̂ne. cipalement le calcul matriciel (programme de Première ES Spécialité)
d’un graphe probabiliste à 2 ou 3 et, pour la dernière partie sur les graphes probabilistes, les notions sur
sommets les suites géométriques (Première ES Obligatoire) et les probabilités
conditionnelles (Terminale ES Obligatoire).

2009-2010 1/6
Théorie des graphes Préparation CAPES UCBL

1 Vocabulaire de base Le graphe 1 est un graphe simple d’ordre 5, de sommets 𝐴, 𝐵, 𝐶, 𝐷

et 𝐸. Les sommets 𝐴 et 𝐵 sont adjacents, 𝐴 et 𝐶 ne le sont pas, 𝐸 est
Définition 1. un sommet isolé.
∙ Un graphe est un ensemble de points et de lignes reliant certains
de ces points. Le graphe 2 est un graphe orienté ayant sept arêtes. Le sommet 𝐸 est
∙ Un sommet du graphe est un point du graphe. Le nombre de som- de degré 3 car trois arêtes partent ou arrivent en 𝑒.
mets est l’ordre du graphe.
∙ Une arête du graphe est une ligne reliant deux sommets. Une Théorème 1. La somme des degrés de tous les sommets d’un
boucle est une arête reliant un sommet à lui-même. graphe est égal au double du nombre total d’arêtes.
∙ Un sommet est isolé lorsque aucune arête de le relie aux autres
sommets.
∙ Un graphe simple est un graphe sans boucle tel que, entre deux Exemple. Dans le graphe 1 précédent, il y a 5 arêtes. La somme des
sommets, il y ait au plus une arête. Deux sommets reliés par une degrés est 2 + 3 + 2 + 3 + 0 = 10 = 2 × 5.
arête sont adjacents.
∙ Un graphe orienté est un graphe dont les arêtes sont orientées. Définition 2. Un graphe complet est un graphe simple dont tous
Une arête orientée va d’un sommet vers un autre sommet, elle est les sommets sont adjacents les uns avec les autres
représentée par une flèche.
∙ Le degré d’un sommet est égal au nombre d’arêtes dont ce sommet Exemple.
est une extrémité.

Exemples.

Le graphe 3 est un graphe complet d’ordre 5.

Dans le graphe complet d’ordre 𝑛 :

∙ le degré de chacun des sommets est 𝑛 − 1
𝑛(𝑛 − 1)
∙ le nombre d’arêtes est
2

2009-2010 2/6
 Théorie des graphes Préparation CAPES UCBL

2 Chaı̂ne et cycle eulériens 3 Matrice d’adjacence d’un graphe

Définition 3. Définition 5.
∙ Une chaı̂ne, dans un graphe non orienté, est une suite d’arêtes ∙ La longueur d’une chaı̂ne est le nombre d’arêtes qui la com-
mises bout à bout reliant deux sommets du graphe. posent.
∙ Une chaı̂ne orientée, dans un graphe orienté, est une suite ∙ La distance entre deux sommets d’un graphe connexe est la lon-
d’arêtes orientées telles que l’extrémité terminale de l’une est l’ex- gueur de la chaı̂ne qui les relie, ayant le moins d’arêtes.
trémité initiale de l’autre. ∙ Le diamètre d’un graphe connexe est la plus grande distance consta-
∙ Un cycle, dans un graphe, est une chaı̂ne dont les extrémités coı̈n- tée entre deux sommets de ce graphe parmi toutes les paires de som-
cident, composée d’arêtes toutes distinctes. Une chaı̂ne est notée mets.
par la liste des sommets où elle passe, reliés par un segment ou une
Exemple.
flèche quand le graphe est orienté.
∙ Un graphe est connexe lorsque, pour chaque paire de sommets, il
existe au moins une chaı̂ne reliant les deux sommets.

Exemples. Dans le graphe 1 précédent, (𝐴, 𝐷, 𝐵, 𝐷, 𝐶) est une chaı̂ne.

Une chaı̂ne orientée du graphe 2 est (𝐵, 𝐴, 𝐶, 𝐴, 𝐷). Le graphe 1 n’est
pas connexe puisqu’il posseède un sommet isolé.

Définition 4. Dans le graphe 4, la distance entre 𝐴 et 𝐷 est 2. Le diamètre du graphe

∙ Une chaı̂ne eulérienne est une chaı̂ne composée de toutes les est 3 (distance entre 𝐴 et 𝐸).
arêtes du graphe, prises une seule fois.
∙ Un cycle eulérien est une chaı̂ne eulérienne dont les extrémités Définition 6. La matrice d’adjacence d’un graphe d’ordre 𝑛
coı̈ncident (resp. graphe orienté d’ordre 𝑛) est la matrice carrée 𝐴 de taille 𝑛 × 𝑛,
dont l’élément 𝑎𝑖,𝑗 est égal au nombre d’arêtes reliant les sommets 𝑖
et 𝑗. (resp. allant du sommet 𝑖 vers le sommet 𝑗).
Théorème 2 (Théorèmes d’Euler).
(i) Un graphe connexe admet une chaı̂ne eulérienne entre les sommets ⎛ ⎞
0 1 1 0 0
𝐴 et 𝐵 si et seulement si 𝐴 et 𝐵 sont les seuls sommets de degré Exemple. Reprenons le graphe 4. ⎜ 1 0 1 1 0 ⎟
impair. Sa matrice d’adjacence est la sui- ⎜ ⎟
⎜ 1 1 0 1 0 ⎟.
(ii) Un graphe connexe admet un cycle eulérien si et seulement si tous vante. Elle est symétrique puisque ⎜ ⎟
⎝ 0 1 1 0 1 ⎠
les sommets sont de degré pair. le graphe n’est pas orienté.
0 0 0 1 0

Exemple. Le graphe 1 admet (𝐵, 𝐶, 𝐷, 𝐵, 𝐴, 𝐷) pour chaı̂ne eulé- Théorème 3. Soit 𝐴 la matrice d’adjacence d’un graphe et soit
rienne mais d’admet pas de cycle eulérien. 𝑝 ≥ 1. Alors, l’élément 𝑝𝑖,𝑗 de la matrice 𝐴𝑝 est égal au nombre de
chaı̂nes de longueur 𝑝 reliant le sommet 𝑖 au sommet 𝑗.

2009-2010 3/6
Théorie des graphes Préparation CAPES UCBL

4 Coloriage des sommets d’un graphe Exemple : Pour le graphe 5, (𝐵, 𝐶, 𝐸, 𝐹 ) est un sous-graphe complet
d’ordre 𝑝 = 4 (il est maximal).
Définition 7. De plus, voici les degrés des sommets :
∙ Un sous-graphe d’un graphe 𝐺 est un graphe composé de sommets
de 𝐺 et de certaines arêtes qui relient ces sommets. sommet 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐺
∙ Un sous-graphe est dit stable lorsqu’il ne comporte aucune arête, degré 4 3 4 2 5 6 4
autrement dit si deux sommets quelconques ne sont pas adjacents.
Ainsi, le plus haut degré est 𝐷 = 6. On sait donc que

Définition 8. 4 ≤ 𝛾(𝐺) ≤ 6 + 1 = 7
Colorier les sommets d’un graphe 𝐺 non orienté, c’est leur attribuer
une couleur de façon à ce que deux sommets adjacents ne soient pas Algorithme de Welsh et Powell : algorithme de coloriage d’un
coloriés de la même couleur. graphe.
Le nombre minimal de couleurs nécessaires est le nombre chroma-
1. On liste les sommets par ordre décroissant des degrés (plusieurs
tique du graphe, noté 𝛾(𝐺).
possibilités).
Par exemple ici, une liste possible est
Théorème 4.
(i) Le nombre chromatique d’un graphe complet est égal à l’ordre du 𝐹 −𝐸−𝐶 −𝐴−𝐺−𝐵−𝐷
graphe.
(ii) Soit 𝐷 le degré maximal des sommets d’un graphe 𝐺, alors 2. On attribue une couleur 𝑐1 au premier sommet de la liste, et
on attribue cette même couleur aux sommets qui ne lui sont pas
𝛾(𝐺) ≤ 1 + 𝐷. adjacents.
Ici, par exemple, on met une couleur 𝑐1 pour 𝐹 . Aucun sommet
(iii) Soit 𝑝 l’ordre d’un sous-graphe complet d’ordre maximal contenu
ne lui est pas adjacent.
dans un graphe, alors
𝑝 ≤ 𝛾(𝐺). 3. On attribue une couleur 𝑐2 au premier sommet non colorié de la
liste et on recommence comme en 2. tant qu’il reste des sommets
non coloriés dans la liste.
Dans notre exemple, on met
– une couleur 𝑐2 à 𝐸 et 𝐷.
– une couleur 𝑐3 à 𝐶 et 𝐴.
– une couleur 𝑐4 à 𝐺 et 𝐵.
On a ainsi un coloriage du graphe 5 en 4 couleurs, donc 𝛾(𝐺) ≤ 4. On
peut donc en déduire que le nombre chromatique du graphe 5 est égal
à 4.

2009-2010 4/6
Théorie des graphes Préparation CAPES UCBL

5 Graphes pondérés 3. Conclusion.

On obtient un graphe dont tous les sommets sont fixés. Le poids
Définition 9. fixé du sommet 𝐺 est le poids de la plus courte chaı̂ne du sommet
∙ Un graphe (orienté ou non) est dit pondéré lorsque ses arêtes sont 𝐷 vers le sommet 𝐺 dans le graphe.
affectées de nombres positifs. Exemple : On cherche à déterminer le plus court chemin entre 𝐷 et 𝐺.
∙ Le poids d’une arête est le nombre positif qui lui est affecté.
∙ Le poids d’une chaı̂ne est la somme des poids des arêtes qui la
composent.
∙ Une plus petite courte chaı̂ne entre deux sommets donnés est
une chaı̂ne de poids minimal parmi toutes les chaı̂nes reliant les
deux sommets.

Algorithme de Dijkstra : algorithme de détermination d’une plus

courte chaı̂ne d’un graphe pondéré entre un sommet 𝐷 et un som- Voici le graphe obtenu après l’algorithme. On écrit à côté de chaque
met 𝐺. sommet le poids (provisoire ou fixé), et le sommet précédent.
1. Etape d’initialisation.
– On fixe le poids du sommet 𝐷 à 0.
– On marque provisoirement chaque sommet adjacent à 𝐷 du
poids de l’arête reliant 𝐷 à ce sommet. Ces sommets sont des
successeurs de 𝐷.
– On marque provisoirement les autres sommets du poids +∞.
2. Etapes d’itérations.
On note 𝑆 l’ensemble des sommets fixés, et 𝑆 l’ensemble des
sommets marqués provisoirement.
Tant que l’ensemble 𝑆 n’est pas vide, on choisit dans 𝑆 le sommet On peut présenter également le résultat dans un tableau où chaque
𝑋 dont le poids marqué provisoirement 𝑝𝑋 est le plus petit. ligne représente une étape de l’algorithme.
– On marque définitivement ce sommet 𝑋 du poids 𝑝𝑋 . On en-
𝐷 𝐴 𝐵 𝐶 𝐸 𝐹 𝐺
lève 𝑋 de 𝑆 et on le place dans 𝑆.
0 3, 𝐷 12, 𝐷 +∞ +∞ +∞ +∞
– On marque provisoirement chaque sommet 𝑌 successeur du
3, 𝐷 12, 𝐷 8, 𝐴 +∞ 38, 𝐴 +∞
sommet 𝑋 par le poids 𝑝𝑌 = 𝑝𝑋 + 𝑝𝑋,𝑌 où 𝑝𝑋,𝑌 est le poids
12, 𝐷 8, 𝐴 18, 𝐶 16, 𝐶 +∞
de l’arête reliant 𝑋 à 𝑌 . Si le poids obtenu 𝑝𝑌 est plus petit
12, 𝐷 18, 𝐶 16, 𝐶 +∞
que le poids marqué provsoirement au sommet 𝑌 , alors on
18, 𝐶 16, 𝐶 29, 𝐹
barre ce poids marqué et on marque 𝑌 du poids 𝑝𝑌 .
– On réitère le procédé tant que l’ensemble des sommets non 18, 𝐶 29, 𝐹
fixés n’est pas vide. 29, 𝐹
La chaı̂ne la plus courte est donc 𝐷 − 𝐴 − 𝐶 − 𝐹 − 𝐺

2009-2010 5/6
 Théorie des graphes Préparation CAPES UCBL

6 Graphes probabilistes et le graphe probabiliste correspondant à la situation est le suivant :

On veut modéliser l’évolution d’un individu pouvant changer aléa-

toirement d’état. On suppose que le passage d’un état à un autre est
toujours régi de la même façon.
A chaque étape 𝑛, on définit une loi de probabilité sur l’ensemble des
états, appelé état probabiliste de l’étape 𝑛, représenté par une matrice
ligne notée ( )
𝑃𝑛 = 𝑎𝑛 𝑏𝑛 𝑐𝑛 . . .

Définition 10.
Un graphe probabiliste est un graphe orienté et pondéré tel que :
∙ les sommets du graphes sont les états possibles 𝐴, 𝐵, 𝐶,. . . Théorème 5. Soit 𝑃0 la matrice représentant l’état probabiliste
∙ le poids d’une arête corientée issue du sommet 𝑖 et allant vers le initial et pour tout 𝑛 ≥ 1, 𝑃𝑛 la matrice représentant l’état probabiliste
sommet 𝑗 est la probabilité conditionnelle d’être à l’état 𝑗 à l’étape à l’étape 𝑛. On a alors pour tout 𝑛 ≥ 0,
𝑛 + 1 sachant que l’état 𝑖 est réalisé à l’étape 𝑛.
La matrice de transition des états d’un graphe probabiliste est une 𝑃𝑛+1 = 𝑃𝑛 𝑀, 𝑃 𝑛 = 𝑃0 𝑀 𝑛
matrice carrée dont les éléments sont les poids des arêtes du graphe.
Pour tout graphe probabiliste d’ordre 2, lorsque 𝑛 devient très grand,
l’état probabiliste 𝑃𝑛 tend vers un état stable 𝑃 indépendant de l’état
Exemple :
initial 𝑃0 . De plus, 𝑃 = 𝑃 𝑀 .
Un élève peut se rend à son lycée par trois chemins 𝐴, 𝐵 et 𝐶. Chaque
jour il peut changer ou non d’iténéraire :
– S’il passe par le chemin 𝐴, le lendemain il prend le chemin 𝐵 Ainsi, si on note au jour 𝑛,
avec proba 0, 5 et le chemin 𝐶 avec proba 0, 2. – 𝑎𝑛 la probabilité que l’élève emprunte le chemin 𝐴,
– S’il passe par le chemin 𝐵, le lendemain il prend le chemin 𝐴 – 𝑏𝑛 la probabilité que l’élève emprunte le chemin 𝐵,
avec proba 0, 1 et le chemin 𝐶 avec proba 0, 6. – 𝑐𝑛 la probabilité que l’élève emprunte le chemin 𝐶,
– S’il passe par le chemin 𝐶, le lendemain il prend le chemin 𝐴 Alors, les probabilités 𝑎𝑛+1 , 𝑏𝑛+1 , 𝑐𝑛+1 vérifient :
avec proba 0, 6 et le chemin 𝐵 avec proba 0, 2. ( ) ( )
La matrice de transition associée est donc 𝑎𝑛+1 𝑏𝑛+1 𝑐𝑛+1 = 𝑎𝑛 𝑏𝑛 𝑐𝑛 𝑀
⎛ ⎞
0, 3 0, 5 0, 2 Dans notre exemple, on a donc
𝑀 = ⎝ 0, 1 0, 3 0, 6 ⎠ ⎧
0, 6 0, 2 0, 2 ⎨ 𝑎𝑛+1 = 0, 3𝑎𝑛 + 0, 1𝑏𝑛 + 0, 6𝑐𝑛
𝑏𝑛+1 = 0, 5𝑎𝑛 + 0, 3𝑏𝑛 + 0, 2𝑐𝑛
𝑐𝑛+1 = 0, 2𝑎𝑛 + 0, 6𝑏𝑛 + 0, 2𝑐𝑛
⎩

Lorsqu’il y a trois états comme dans cet exemple, on ne peut pas

conclure sur la limite de l’état probabiliste 𝑃𝑛 .

2009-2010 6/6