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 questionsFigure fournieCorrigé 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. Idée : l'ordre est le nombre de sommets ; le degré, le nombre d'arêtes incidentes. Ordre $5$ . $\deg A=3$ ( $AB,EA,AC$ ), $\deg B=2$ , $\deg C=3$ ( $BC,CD,AC$ ), $\deg D=2$ , $\deg E=2$ . Contrôle : la somme des degrés $3+2+3+2+2=12$ vaut deux fois le nombre d'arêtes ( $6$ ).

2. Idée : connexe $=$ une chaîne entre deux sommets quelconques. La chaîne $A-B-C-D-E-A$ visite les cinq sommets ; deux sommets quelconques sont donc reliés : $\Gamma$ est connexe.

3. Idée : théorème d'Euler. $\Gamma$ est connexe avec exactement deux sommets de degré impair ( $A$ et $C$ ) : il admet une chaîne eulérienne d'extrémités $A$ et $C$ , par exemple $A-B-C-D-E-A-C$ (les six arêtes, chacune une fois). Un cycle eulérien exigerait que tous les degrés soient pairs : il n'en existe pas.

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. Idée : parité des degrés. $\deg A=\deg D=1$ , $\deg B=\deg C=2$ . $H$ est connexe (c'est une chaîne) avec exactement deux sommets impairs : il admet une chaîne eulérienne ( $A-B-C-D$ elle-même) mais pas de cycle eulérien.

2. Idée : rendre tous les degrés pairs sans casser la connexité. En ajoutant $AD$ , $\deg A=\deg D=2$ : tous les degrés sont pairs, le graphe reste connexe, donc il admet un cycle eulérien : $A-B-C-D-A$ . C'est la seule arête qui corrige les deux sommets impairs d'un coup.

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. Idée : compter les sommets. Ordre $4$ .

2. Idée : complet $=$ toutes les paires de sommets sont adjacentes ; il faudrait $\binom42=6$ arêtes. Il n'y a que cinq arêtes et $C$ , $D$ ne sont pas adjacents : $K$ n'est pas complet. C'est $K_4$ privé d'une arête.

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