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.

Ce qui aide à reconnaître la démarche

« Justifier que le graphe G est connexe »

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

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

Besoin d’un point de départ ? Voir la méthode

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

Les pièges à vérifier dans ta démarche

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

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.

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

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

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

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.

2 Drill GR-A.2 — Ordre et graphe complet

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.

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

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

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

Changer d’énoncé, garder le raisonnement

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

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

Drill GR-A.2 — Ordre et graphe complet

Relier ce raisonnement au bac