Problème exposition bancs (Tle ES spé) — Les-mathematiques.net The most powerful custom community solution in the world

Problème exposition bancs (Tle ES spé)

Bonsoir
Pouvez-vous m'aider à l'exercice suivant svp ?

Une exposition est organisée dans un parc où 5 bancs sont reliés entre eux par des allées. La fréquentation étant importante on décide d'instaurer un plan de circulation. Certaines allées sont à sens unique et d'autres à double sens. On modélise les bancs par les sommets A, B, C, D, E et les allées par les arêtes du graphe orienté G de la figure suivante.

QUESTION.
1. a) Donner la matrice d'adjacence M associée au graphe G (classer les sommets dans l'ordre alphabétique)
b) Déterminer la matrice M5

2.a) Combien y a-t-il de chemins de longueur 5 partant de A et arrivant en A ? Le graphe admet-il un circuit hamiltonien ?
b) Combien y a-t-il de chemins de longueur 5
* partant de A ?
* arrivant en A ?
* partant de C et arrivant en E ?

c) Combien y a-t-il de chemins de longueur 5 partant de B et arrivant en B ?
Énumérer tous ces chemins et dire combien d'entre eux sont des circuits élémentaires. Pouvait-on s'attendre à ce résultat et pourquoi ?

Mes réponses
1.a) M = (
0 1 0 0 1
0 0 1 1 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0 )
b) M[sup]5[/sup] = 
 1  6  9  6 10
 4  5  7 11  5
 4  6  6 11  5
 1  5 10  6 10
 6  5  5 14  2 )
Désolé je ne sais pas écrire une matrice sur le forum, j'espère que c'est assez clair

2.a) Il n'y a qu'une seule chaîne de longueur 5 qui est la suivante: A-B-C-D-E-A
Je pense qu'il y a un circuit hamiltonien car les arcs sont distincts (est-ce correct et suffisant pour justifier ?

b) D'après la matrice M5, il y a :
32 chemins partant de A
16 chemin arrivant en A
5 chemins partant de C et arrivant en E
(est-ce correct ? Dois-je les énumérer à votre avis ?

c) Il y a 5 chemins qui sont les suivants
B-C-D-E-A-B
B-C-B-D-C-B
B-D-C-B-C-B
B-D-E-D-C-B

Ensuite je ne sais pas comment répondre pour la suite de cette question
Merci pour votre aide :)84108

Réponses

  • La matrice d'adjacence est correcte donc je suppose que la puissance 5 est juste.
    Les sommets sont distincts, pas les arêtes.
    N'énumère pas les 32 chemins ni les autres, c'est inutile (et on ne te le demande pas).
    C'est quoi, un circuit élémentaire ?
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!