cours terminale ES enseignement de spécialité

Introduction à la théorie des graphes

II - chaînes, cycles ; connexité

Les graphes sont souvent utilisés pour modéliser des problèmes associés à des parcours ou à des successions d'actions. Pour cela, on introduit la notion de chaîne.

1 - Définitions

Soit $G = (S A)$ un graphe non orienté. Une chaîne est une liste finie et alternée de sommets et d'arêtes, débutant et finissant par des sommets, telle que chaque arête est incidente avec les sommets qui l'encadrent dans la liste.
Le premier et le dernier élément de la liste sont les extrémités initiale et finale de la chaîne.

Si le graphe est simple, on peut définir une chaîne par la liste de ses sommets ou de ses arêtes.

La longueur d'une chaîne est égale au nombre d'arêtes qui la composent.
Une chaîne dont toutes les arêtes sont distinctes est une chaîne simple.
Une chaîne dont tous les sommets (sauf peut-être les extrémités) sont distincts est une chaîne élémentaire.
Une chaîne est fermée si l'origine et l'extrémité finale de la chaîne sont confondues.
Une chaîne fermée est un cycle si elle est composées d'arêtes toutes distinctes.

remarque

Les définitions précédentes, peuvent être transposées au cas des graphes orientés. On parlera de chaîne orientée ou chemin et de cycle orienté ou circuit.

exemple

Dans le graphe ci-contre :

La chaîne ${s_{0}; s_{1}; s_{0}; s_{2}; s_{0}; s_{3}; s_{0}; s_{4}; s_{0}; s_{5}; s_{0}}$ est une chaîne fermée de longueur 10.
La chaîne ${s_{1}; s_{2}; s_{3}; s_{0}; s_{4}; s_{5}}$ est une chaîne élémentaire de longueur 5.
La chaîne ${s_{1}; s_{2}; s_{0}; s_{3}; s_{4}; s_{0}; s_{5}; s_{1}}$ est un cycle de longueur 7.

2 - Chaînes de longueur donnée

nombre de chaînes

Soit G un graphe et M sa matrice d'adjacence.
Le nombre de chaînes de longueur n joignant le sommet i au sommet j est donné par le terme d'indice i , j de la matrice $M^{n}$ .

distance

Soit G un graphe ; si x et y sont deux sommets de G, la distance de x à y notée $d (x; y)$ , est la longueur d'une plus courte chaîne de G reliant x à y.

remarques

La distance d'un sommet à lui même est nulle.
S'il n'existe pas de chaînes joignant deux sommets x et y, la distance de x à y est infinie.

diamètre

On appelle diamètre d'un graphe la plus grande des distances entre deux sommets du graphe.

exemple

Soit $M = (\begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{matrix})$ la matrice d'adjacence du graphe G ci-contre

Déterminons la matrice des distances D du graphe, dont le coefficient $d_{i, j}$ est égal à la distance entre les sommets i et j.
La distance d'un sommet à lui même est nulle et, on utilise le symbole ∞ pour indiquer que la distance entre deux sommets n'est pas encore fixée : $D = (\begin{matrix} 0 & \infty & \infty & \infty & \infty & \infty \\ \infty & 0 & \infty & \infty & \infty & \infty \\ \infty & \infty & 0 & \infty & \infty & \infty \\ \infty & \infty & \infty & 0 & \infty & \infty \\ \infty & \infty & \infty & \infty & 0 & \infty \\ \infty & \infty & \infty & \infty & \infty & 0 \end{matrix})$

La matrice $M = (\begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{matrix})$ donne les distances égales à 1 : $D = (\begin{matrix} 0 & 1 & \infty & \infty & \infty & \infty \\ 1 & 0 & 1 & \infty & \infty & \infty \\ \infty & 1 & 0 & 1 & 1 & \infty \\ \infty & \infty & 1 & 0 & 1 & 1 \\ \infty & \infty & 1 & 1 & 0 & 1 \\ \infty & \infty & \infty & 1 & 1 & 0 \end{matrix})$
La matrice $M^{2} = (\begin{matrix} 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 1 & 1 & 0 \\ 1 & 0 & 3 & 1 & 1 & 2 \\ 0 & 1 & 1 & 3 & 2 & 1 \\ 0 & 1 & 1 & 2 & 3 & 1 \\ 0 & 0 & 2 & 1 & 1 & 2 \end{matrix})$ donne les distances égales à 2 : $D = (\begin{matrix} 0 & 1 & 2 & \infty & \infty & \infty \\ 1 & 0 & 1 & 2 & 2 & \infty \\ 2 & 1 & 0 & 1 & 1 & 2 \\ \infty & 2 & 1 & 0 & 1 & 1 \\ \infty & 2 & 1 & 1 & 0 & 1 \\ \infty & \infty & 2 & 1 & 1 & 0 \end{matrix})$
La matrice $M^{3} = (\begin{matrix} 0 & 2 & 0 & 1 & 1 & 0 \\ 2 & 0 & 4 & 1 & 1 & 2 \\ 0 & 4 & 2 & 6 & 6 & 2 \\ 1 & 1 & 6 & 4 & 5 & 5 \\ 1 & 1 & 6 & 5 & 4 & 5 \\ 0 & 2 & 2 & 5 & 5 & 2 \end{matrix})$ donne les distances égales à 3 : $D = (\begin{matrix} 0 & 1 & 2 & 3 & 3 & \infty \\ 1 & 0 & 1 & 2 & 2 & 3 \\ 2 & 1 & 0 & 1 & 1 & 2 \\ 3 & 2 & 1 & 0 & 1 & 1 \\ 3 & 2 & 1 & 1 & 0 & 1 \\ \infty & 3 & 2 & 1 & 1 & 0 \end{matrix})$
La matrice $M^{4} = (\begin{array}{r} 2 & 0 & 4 & 1 & 1 & 2 \\ 0 & 6 & 2 & 7 & 7 & 2 \\ 4 & 2 & 16 & 10 & 10 & 12 \\ 1 & 7 & 10 & 16 & 15 & 9 \\ 1 & 7 & 10 & 15 & 16 & 9 \\ 2 & 2 & 12 & 9 & 9 & 10 \end{array})$ donne les distances égales à 4 : $D = (\begin{matrix} 0 & 1 & 2 & 3 & 3 & 4 \\ 1 & 0 & 1 & 2 & 2 & 3 \\ 2 & 1 & 0 & 1 & 1 & 2 \\ 3 & 2 & 1 & 0 & 1 & 1 \\ 3 & 2 & 1 & 1 & 0 & 1 \\ 4 & 3 & 2 & 1 & 1 & 0 \end{matrix})$

La plus grande des distances entre deux sommets du graphe est 4 donc le diamètre du graphe est 4.

3 - Connexité

Un graphe G est connexe s'il existe au moins une chaîne entre deux sommets quelconques G.

Autrement dit : Un graphe est connexe si on peut atteindre n'importe quel sommet à partir d'un sommet quelconque en parcourant différentes arêtes.

algorithme

L'algorithme suivant permet de déterminer tous les sommets qui peuvent être atteints à partir d'un sommet.

Marquer provisoirement (au crayon) le sommet x ;

Tant que des sommets sont provisoirement marqués

choisir un sommet y provisoirement marqué ;
marquer provisoirement les sommets adjacents non marqués ;
marquer définitivement (à l'encre) y ;

Fin Tant que

Si tous les sommets sont définitivement marqués alors le graphe est connexe, sinon on a obtenu la classe de connexité du sommet x.

exemple

Considérons le graphe ci-dessous

La figure suivante illustre cet algorithme sur le graphe précédent.


Le sommet $s_{1}$ étant marqué, on marque provisoirement les sommets adjacents $s_{3}$ et $s_{5}$ .	On marque provisoirement les sommets $s_{5}$ et $s_{9}$ adjacents au sommet $s_{3}$ définitivement marqué.	On marque provisoirement les sommets $s_{8}$ et $s_{9}$ adjacents au sommet $s_{5}$ définitivement marqué.	Les sommets $s_{8}$ et $s_{9}$ sont définitivement marqués, il n'y a plus de sommets provisoirement marqués.

Le graphe n'est pas connexe, il n'existe pas de chaîne entre les sommets $s_{1}$ et $s_{2}$ .

4 - Cycle eulérien

définition

Un cycle eulérien (respectivement une chaîne eulérienne) dans un graphe G est un cycle (respectivement une chaîne) contenant chaque arête de G une et une seule fois.

théorème 1

Un graphe connexe admet un cycle eulérien si, et seulement si, tous ses sommets ont un degré pair.

démonstration

Si le graphe possède 0 ou 1 sommet, la preuve est triviale, on suppose donc que l'ordre du graphe est supérieur ou égal à 2.

Si le graphe connexe admet un cycle eulérien alors en chaque sommet le cycle eulérien « entrant » dans le sommet doit « ressortir » et comme les arêtes du cycle ne peuvent être utilisées qu'une fois, chaque sommet est de degré pair.

Réciproquement :

Soit G un graphe connexe dont tous les sommets sont de degré pair.
Comme G possède au moins deux sommets, tous les sommets de G sont de degré supérieur ou égal à 2. Ceci implique qu'il existe au moins un cycle dans G.

Formons un cycle $C_{1}$ dans G ( chaîne fermée dont toutes les arêtes sont distinctes ).

Si $C_{1}$ contient toutes les arêtes du graphe alors G admet un cycle eulérien et le théorème est démontré.
Dans le cas contraire, le sous graphe H de G défini par les arêtes non utilisées par $C_{1}$ a tous ses sommets de degré pair, le cycle contenant un nombre pair d'arêtes incidentes pour chaque sommet.
Comme G est connexe, H possède au moins un sommet commun avec le cycle $C_{1}$ . Soit $x_{i}$ un tel sommet.
Construisons alors, de la même manière que précédemment, un cycle $C_{2}$ dans H à partir de $x_{i}$ .
En insérant dans le cycle $C_{1}$ à partir du sommet $x_{i}$ le cycle $C_{2}$ ,on obtient un cycle ${C'}_{1}$ . Si ce cycle contient toutes les arêtes de G, ${C'}_{1}$ est le cycle eulérien cherché.
Sinon, on continue ce processus, qui se terminera car les sommets du graphe G sont en nombre fini.

théorème 2

Un graphe connexe possède une chaîne eulérienne si, et seulement si, le nombre de sommets de degré impair est égal à 0 ou 2.
Si le nombre de sommets de degré impair est égal à 2, alors les deux sommets de degré impair sont les extrémités de la chaîne eulérienne.

démonstration

Soit G un graphe connexe. Si le nombre de sommets de degré impair est nul, alors le graphe G admet un cycle eulérien.

Si le nombre de sommets de degré impair est égal à 2. Soient $s_{i}$ et $s_{j}$ les deux sommets de degré impair.
Le graphe G' obtenu en ajoutant l'arête $s_{i}, s_{j}$ au graphe G est connexe et tous ses sommets sont de degré pair. G' admet un cycle eulérien dont l'origine est le sommet $s_{i}$ .

Par conséquent G contient une chaîne eulérienne qui commence en $s_{i}$ et se termine en $s_{j}$ .

algorithme

Les démonstrations précédentes permettent de construire une chaîne eulérienne dans un graphe connexe dont le nombre de sommets de degré impair est 0 ou 2.

Si deux sommets sont de degré impair Alors
construire une chaîne simple C ayant pour extrémités ces deux sommets ;
Fin Si

Si tous les sommets sont de degré pair Alors
construire un cycle C à partir d'un sommet quelconque ;
Fin Si

marquer les arêtes de C ;

Tant que il reste des arêtes non marquées

choisir un sommet x de C ;
Si il existe un cycle d'origine x ne contenant aucune des arêtes marquées Alors
marquer les arêtes du cycle d'origine x ;
remplacer dans C le sommet x par le cycle d'origine x ;
Fin Si

Fin Tant que

exemple

Le cycle ${s_{1}; s_{6}; s_{5}; s_{7}; s_{3}; s_{4}; s_{2}; s_{1}}$ contient tous les sommets du graphe G ci-contre donc G est connexe.

Le graphe est connexe et il n'y a que deux sommets de degré impair $s_{1}$ et $s_{5}$ par conséquent, il existe une chaîne eulérienne d'extrémités $s_{1}$ et $s_{5}$ .

ÉTAPE 1

Les deux sommets de degré impair étant $s_{1}$ et $s_{5}$ , on construit une chaîne simple joignant ces deux sommets. Par exemple $C = {s_{1}; s_{2}; s_{6}; s_{3}; s_{4}; s_{5}}$

ÉTAPE 2

Le cycle simple $C_{1} = {s_{2}; s_{4}; s_{1}; s_{6}; s_{5}; s_{2}}$ ne contient aucune des arêtes de la chaîne C.
On fusionne la chaîne C avec le cycle $C_{1}$ en remplaçant le sommet $s_{2}$ dans la chaîne C par le cycle $C_{1}$ . $C = {s_{1}; s_{2}; s_{4}; s_{1}; s_{6}; s_{5}; s_{2}; s_{6}; s_{3}; s_{4}; s_{5}}$

Il reste encore des arêtes non marquées, on recommence l'étape 2

Le cycle simple $C_{2} = {s_{3}; s_{7}; s_{5}; s_{3}}$ ne contient aucune des arêtes de la chaîne C.
On fusionne la chaîne C avec le cycle $C_{2}$ en remplaçant le sommet $s_{3}$ dans la chaîne C par le cycle $C_{2}$ . $C = {s_{1}; s_{2}; s_{4}; s_{1}; s_{6}; s_{5}; s_{2}; s_{6}; s_{3}; s_{7}; s_{5}; s_{3}; s_{4}; s_{5}}$

Toutes les arêtes sont marquées. La chaîne C est une chaîne eulérienne.

remarque

La chaîne eulérienne C n'est pas unique, il existe d'autres choix possibles par exemple :

Graphes : premières définitions <<précédent | suivant>> Algorithme de Dijkstra

[ Accueil ]

Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.