GR-DThéorie des graphes

Degrés, sous-graphe complet, eulérien et chemins via M^n

Idée directrice

Lire un graphe : degrés des sommets, sous-graphe complet (clique), chaîne eulérienne (0 ou 2 sommets de degré impair), et nombre de chemins de longueur $n$ via $M^n$ .

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

« sous graphe complet d'ordre 3 »

« chaîne eulérienne »

« chemins de longueur 5 »

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué

Soit un graphe $(G)$ connexe dont les degrés des sommets $A,B,C,D,E$ sont $2,3,2,3,2$ (esprit bac éco-gestion 2021 principale).

On observe que $\{B,C,D\}$ induit un sous-graphe complet d'ordre 3. Que peut-on en déduire pour le nombre chromatique $\gamma(G)$ (bornes) ?
Le graphe est connexe et exactement deux sommets ( $B$ et $D$ ) sont de degré impair. Conclure sur l'existence d'une chaîne eulérienne.
Si $M$ est la matrice d'adjacence, où lit-on le nombre de chemins de longueur 5 de $D$ vers $B$ ?

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

1. Clique d'ordre 3 ⇒ $\gamma(G)\ge 3$ . Degré max $\Delta=3$ ⇒ $\gamma(G)\le\Delta+1=4$ . Avec l'analyse du corrigé on obtient $\gamma(G)=3$ (corrigé 2021 : sous-graphe complet d'ordre 3 et $\gamma\le 3+1$ ).

2. Théorème d'Euler : un graphe connexe admet une chaîne eulérienne ssi 0 ou 2 sommets de degré impair. Ici exactement 2 ⇒ chaîne eulérienne (corrigé 2021).

3. Coefficient $(M^5)_{DB}$ (ligne de $D$ , colonne de $B$ ) — corrigé : intersection ligne 5 / colonne 2 selon la numérotation des sommets dans $M$ .

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

Entraînement 01 / 01

Drill GR-D.1 — Critère eulérien

1 questionCorrigé masqué

Un graphe connexe a exactement deux sommets de degré impair. Admet-il une chaîne eulérienne ? un circuit eulérien ? Justifiez en une phrase chaque réponse.

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

Oui pour une chaîne eulérienne (exactement 0 ou 2 degrés impairs). Non pour un circuit eulérien (il faudrait tous les degrés pairs). C'est le critère utilisé dans le corrigé 2021 éco-gestion (« deux sommets exactement … degré impair donc … chaîne eulérienne »).

Méthode / Automatismes

Eulérien circuit : tous degrés pairs ; chaîne : 0 ou 2 impairs.
$(M^n)_{ij}$ = nombre de chemins de longueur $n$ de $i$ vers $j$ .

Pièges classiques

Confondre chaîne et circuit eulériens ; lire $M^5$ sans respecter l'ordre des sommets.