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=SA 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.

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

Graphe : L'illustration svg n'est pas visible par votre navigateur.

Dans le graphe ci-contre :


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 Mn.

distance

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

remarques

diamètre

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

exemple

Graphe : L'illustration svg n'est pas visible par votre navigateur.

Soit M=010000101000010110001011001101000110 la matrice d'adjacence du graphe G ci-contre

Déterminons la matrice des distances D du graphe, dont le coefficient di,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=000000


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

Graphe : L'illustration svg n'est pas visible par votre navigateur.

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

Connexité sommets adjacents : L'illustration svg n'est pas visible par votre navigateur.Connexité sommets adjacents : L'illustration svg n'est pas visible par votre navigateur.Connexité sommets adjacents : L'illustration svg n'est pas visible par votre navigateur.Connexité sommets adjacents : L'illustration svg n'est pas visible par votre navigateur.
Le sommet s1 étant marqué, on marque provisoirement les sommets adjacents s3 et s5.On marque provisoirement les sommets s5 et s9 adjacents au sommet s3 définitivement marqué.On marque provisoirement les sommets s8 et s9 adjacents au sommet s5 définitivement marqué.Les sommets s8 et s9 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 s1 et s2.

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 C1 dans G ( chaîne fermée dont toutes les arêtes sont distinctes ).

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 si et sj les deux sommets de degré impair.
Le graphe G' obtenu en ajoutant l'arête si,sj 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 si.

Par conséquent G contient une chaîne eulérienne qui commence en si et se termine en sj.

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

Graphe : L'illustration svg n'est pas visible par votre navigateur.

Le cycle s1s6s5s7s3s4s2s1 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 s1 et s5 par conséquent, il existe une chaîne eulérienne d'extrémités s1 et s5.


ÉTAPE 1

Graphe : L'illustration svg n'est pas visible par votre navigateur.

Les deux sommets de degré impair étant s1 et s5, on construit une chaîne simple joignant ces deux sommets. Par exemple C=s1s2s6s3s4s5


ÉTAPE 2

Graphe : L'illustration svg n'est pas visible par votre navigateur.

Le cycle simple C1=s2s4s1s6s5s2 ne contient aucune des arêtes de la chaîne C.
On fusionne la chaîne C avec le cycle C1 en remplaçant le sommet s2 dans la chaîne C par le cycle C1.C=s1s2s4s1s6s5s2s6s3s4s5

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


Graphe : L'illustration svg n'est pas visible par votre navigateur.

Le cycle simple C2=s3s7s5s3 ne contient aucune des arêtes de la chaîne C.
On fusionne la chaîne C avec le cycle C2 en remplaçant le sommet s3 dans la chaîne C par le cycle C2.C=s1s2s4s1s6s5s2s6s3s7s5s3s4s5

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 :

Graphe : L'illustration svg n'est pas visible par votre navigateur.

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.