Connexité, chaînes, cycles et tracé d'un graphe
Compte les composantes connexes, trouve les sommets de degré impair et décide si un graphe peut être tracé sans lever le crayon.
📖 Commence ici : lis les étapes de la « Leçon » dans l’ordre (1, 2, 3 …) et réponds à chaque question. Ensuite, passe à l’« Entraînement ».
- Russie : classe 7
Conseils pour les adultes
Ce thème se travaille en Terminale, option mathématiques expertes (graphes et matrices) : après les sommets, les arêtes et le degré viennent la chaîne (suite d'arêtes où chacune commence là où la précédente finit), le cycle (chaîne qui revient à son point de départ) et la connexité (deux sommets quelconques sont reliés par une chaîne). Tout graphe se découpe en composantes connexes.
Une chaîne eulérienne passe par chaque arête exactement une fois. Elle existe quand le graphe est connexe et qu'il a zéro ou deux sommets de degré impair. Avec zéro, il existe un cycle eulérien ; avec deux, la chaîne part de l'un et finit à l'autre. C'est ce qui règle le problème des ponts de Königsberg (quatre sommets impairs) et la question « peut-on tracer cette figure sans lever le crayon ? ».
Erreurs fréquentes : ne pas compter un sommet isolé comme une composante ; compter les sommets au lieu des arêtes pour le degré ; croire que toute figure peut se tracer d'un seul trait.