GR-AThéorie des graphes

Connexité, degrés, chaîne et cycle eulériens

Idée directrice

Le graphe non orienté de l'épreuve Eco-Gestion se lit d'abord par ses sommets et arêtes : ordre, degrés, connexité, puis critère d'eulérien (chaîne eulérienne $\Leftrightarrow$ connexe et exactement $0$ ou $2$ sommets de degré impair ; cycle eulérien $\Leftrightarrow$ tous les degrés pairs). Attesté 2018–2022.

Signature de reconnaissance — l'énoncé se trahit ainsi

« Justifier que le graphe G est connexe »

« chaîne eulérienne » / « cycle eulérien »

« Recopier et compléter le tableau des degrés »

Sujet principal

Exercice — parcours eulérien d'un réseau de boutiques

3 questionsCorrigé masqué

On modélise un petit centre commercial par le graphe non orienté $\Gamma$ de sommets $A,B,C,D,E$ et d'arêtes $AB,BC,CD,DE,EA,AC$ .

Donner l'ordre du graphe $\Gamma$ et compléter le tableau des degrés des sommets.
Justifier que $\Gamma$ est connexe.
Justifier que $\Gamma$ admet une chaîne eulérienne et en donner un exemple. Admet-il un cycle eulérien ?

Voir la correction commentéeAprès avoir posé votre démarche

1. On pose l'ordre : le graphe $\Gamma$ a $5$ sommets. On a : $\deg(A)=3$ (arêtes $AB,EA,AC$ ), $\deg(B)=2$ ( $AB,BC$ ), $\deg(C)=3$ ( $BC,CD,AC$ ), $\deg(D)=2$ ( $CD,DE$ ), $\deg(E)=2$ ( $DE,EA$ ).

2. On sait que la chaîne $A-B-C-D-E-A$ visite tous les sommets. Par suite le graphe $\Gamma$ est connexe.

3. On a : $\Gamma$ est connexe et possède exactement deux sommets de degré impair ( $A$ et $C$ ). D'où $\Gamma$ admet une chaîne eulérienne d'extrémités $A$ et $C$ . Exemple : $A-B-C-D-E-A-C$ . Comme il existe des degrés impairs, $\Gamma$ n'admet pas de cycle eulérien.

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 02

Drill GR-A.1 — Cycle eulérien par ajout d'arête

2 questionsCorrigé masqué

Soit le graphe non orienté $H$ de sommets $A,B,C,D$ et d'arêtes $AB,BC,CD$ uniquement (chaîne $A-B-C-D$ ).

Dresser le tableau des degrés. Justifier que $H$ admet une chaîne eulérienne mais pas de cycle eulérien.
Quelle arête ajouter pour obtenir un cycle eulérien ? Justifier.

Voir la correction commentéeAprès avoir posé votre démarche

1. On a : $\deg(A)=1$ , $\deg(B)=2$ , $\deg(C)=2$ , $\deg(D)=1$ . Le graphe $H$ est connexe (c'est une chaîne) et a exactement deux sommets de degré impair. Par suite il admet une chaîne eulérienne (d'extrémités $A$ et $D$ ). Il n'admet pas de cycle eulérien car des degrés impairs subsistent.

2. On ajoute l'arête $AD$ . Alors $\deg(A)=\deg(D)=2$ et tous les degrés sont pairs. Le graphe reste connexe, donc il admet un cycle eulérien (le cycle $A-B-C-D-A$ ).

Entraînement 02 / 02

Drill GR-A.2 — Ordre et graphe complet

2 questionsCorrigé masqué

Soit le graphe non orienté $K$ de sommets $A,B,C,D$ dont les arêtes sont $AB,AC,AD,BC,BD$ (pas d'arête $CD$ ).

Quel est l'ordre de $K$ ?
$K$ est-il complet ? Pourquoi ?

Voir la correction commentéeAprès avoir posé votre démarche

1. On pose l'ordre du graphe $K$ : il y a $4$ sommets $A,B,C,D$ . On obtient $|V(K)|=4$ .

2. On a : les sommets $C$ et $D$ ne sont pas adjacents (l'arête $CD$ est absente de la liste). Un graphe complet d'ordre $4$ exigerait les six arêtes possibles. Par suite $K$ n'est pas un graphe complet : il manque au moins $CD$ .

Méthode / Automatismes

Dresser d'abord le tableau sommet / degré.
Connexité : exhiber une chaîne qui touche tous les sommets (ou argumenter l'absence d'isolé).
Eulérien : compter les degrés impairs (0 → cycle ; 2 → chaîne ; sinon rien).

Pièges classiques

Confondre chaîne eulérienne (toutes les arêtes) et chaîne hamiltonienne (tous les sommets). Oublier l'hypothèse de connexité. Compter deux fois une arête dans le degré.