mathématiques appliquées (ECG 1re année) · Chapitre 3 · Exercice d'entraînement
Compter toutes les chaînes de longueur
Théorie des graphes · Chemins et puissances de la matrice · niveau 3 (difficile)
Énoncé
Soit un graphe à sommets, de matrice d'adjacence . Montrer que la somme de tous les coefficients de est le nombre total de chaînes de longueur du graphe. Calculer ce nombre pour le graphe complet , et l'appliquer à avec .
Pour démarrer : comment l'IA t'aide
Élève
Je sais que compte les chaînes de longueur de à . Pour la somme de tous les coefficients, il suffit d'additionner, non ? Je ne vois pas ce qu'il y a à démontrer.
IA
Additionner donne le total à condition de ne compter aucune chaîne deux fois et de n'en oublier aucune. Une chaîne de longueur donnée, dans combien de coefficients est-elle comptée ?
Élève
Dans un seul : celui dont est son sommet de départ et son sommet d'arrivée.
IA
Exactement. Qu'en déduis-tu sur les ensembles de chaînes comptés par deux coefficients différents, et pourquoi leur réunion contient-elle toutes les chaînes ? Ensuite, pour , plutôt que de calculer , comment compter directement les suites de sommets ?
L'IA ne donne pas la réponse : elle pose la question qui fait avancer. Le corrigé de cet exercice n'est pas publié : à toi de continuer.
Continue cet exercice avec l'IA
Reprends l'exercice là où le dialogue s'arrête.
Continuer avec l'IA — gratuit, sans inscriptionGratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.