Naïma fait partie d'une école de musique. En vue du spectacle de fin d'année, elle souhaite déposer à vélo des affiches publicitaires sur les panneaux de sa ville. Les pistes cyclables reliant ces panneaux sont représentées sur le graphe 𝒢 ci-dessous.
Le sommet E désigne son école de musique, le sommet S la salle de spectacle et les sommets A, B, C, et D les panneaux d'affichage.
Déterminer, en justifiant la réponse, si le graphe 𝒢 est :
complet ;
Les sommets A et B ne sont pas ajacents donc le graphe n'est pas complet.
connexe.
La chaîne fermée A - E - B - C - D - S - A contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets du graphe il existe au moins une chaîne les reliant donc le graphe est connexe.
Naïma pourra-t-elle déposer ses affiches sur tous les panneaux en allant de son école de musique à la salle de spectacle et en empruntant une et une seule fois chaque piste cyclable ?
Justifier la réponse. Si un tel trajet existe, en citer un.
Les degrés des sommets sont :
Sommets | A | B | C | D | E | S |
Degré | 2 | 4 | 2 | 4 | 3 | 3 |
Le graphe est connexe et il n'y a que deux sommets E et S de degré impair, il existe donc des chaînes eulérienne d'extrémités E et S.
Naïma pourra déposer ses affiches sur tous les panneaux en allant de son école de musique à la salle de spectacle et en empruntant une et une seule fois chaque piste cyclable.
Par exemple le trajet E - B - S - D - B - C - D - E - A - S.
Donner la matrice d'adjacence M liée à ce graphe dans laquelle les sommets seront classés dans l'ordre suivant : E, A, B, C, D, S.
La matrice d'adjacence du graphe est
On donne la matrice incomplète : .
Déterminer les coefficients manquants de la matrice , en détaillant les calculs.
Le coefficient de la quatrième ligne et première colonne de la matrice est égal au produit de la quatrième ligne de la matrice M par la première colonne de la matrice M :
Le graphe 𝒢 n'est pas orienté par conséquent, la matrice est symétrique par rapport à la diagonale. Il s'ensuit que le coefficient de la première ligne et quatrième colonne de la matrice est égal au coefficient .
Ainsi, .
Combien existe-t-il de chemins permettant de se rendre de l'école de musique à la salle de spectacle en empruntant exactement deux pistes cyclables ?
Le coefficient de la première ligne et sixième colonne de la matrice est égal au nombre de chemins permettant de se rendre de l'école de musique E à la salle de spectacle S en empruntant exactement deux pistes cyclables.
donc il y a trois trajets permettant de se rendre de l'école de musique à la salle de spectacle en empruntant exactement deux pistes cyclables.
Lorsqu'elle a déposé ses affiches, Naïma a relevé le temps de trajet entre chaque panneau d'affichage. Le graphe ci-dessous indique ces durées, exprimées en minutes.
Indiquer, à l'aide d'un algorithme, le chemin permettant à Naïma de se rendre le plus rapidement possible de son école de musique à la salle de spectacle le soir de la représentation.
Donner la durée de ce parcours.
À l'aide de l'algorithme de Dijkstra, déterminons le trajet qui minimise le temps de parcours pour se rendre de l'école de musique à la salle de spectacle.
E | A | B | C | D | S | Sommet sélectionné |
0 | ∞ | ∞ | ∞ | ∞ | ∞ | E (0) |
9 (E) | 4 (E) | ∞ | 7 (E) | ∞ | B (4) | |
9 (E) | 6 (B) | 5 (B) | 12 (B) | D (5) | ||
9 (E) | 6 (B) | 8 (D) | C (6) | |||
9 (E) | 8 (D) | S (8) |
Le sommet S étant marqué, pour lire la chaîne de poids minimal, on part de S et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet permettant à Naïma de se rendre le plus rapidement possible de son école de musique à la salle de spectacle est E - B - D - S pour une durée de 8 minutes.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.