Six villes A , B , C , D , E , F sont reliées par des routes directes comme suit : A B , A C , B D , B E , C D , C F , D E , E F . Construire la matrice d'adjacence M de ce graphe. Sans calculer M 2 entièrement, déterminer le nombre de chemins de longueur 2 entre A et D . Un voyageur veut partir d'une ville, emprunter chaque route exactement une fois, et revenir à son point de départ. Est-ce possible ?

Modélisation par graphe — réseau de villes

Intermédiaire Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Six villes $A, B, C, D, E, F$ sont reliées par des routes directes comme suit : $A B, A C, B D, B E, C D, C F, D E, E F$ .

Construire la matrice d'adjacence $M$ de ce graphe.
Sans calculer $M^{2}$ entièrement, déterminer le nombre de chemins de longueur 2 entre $A$ et $D$ .
Un voyageur veut partir d'une ville, emprunter chaque route exactement une fois, et revenir à son point de départ. Est-ce possible ?

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Validez votre réponse pour enregistrer votre progression et gagner des points