Deux amis, Louisa et Antoine, passent la journée dans un parc d'attraction.
Le plan du parc est donné par le graphe Γ ci-dessous. Les arêtes de ce graphe représentent les allées du parc et les sommets correspondent aux intersections de ces allées. On a pondéré les arêtes de ce graphe par les temps de parcours en minutes.
Le graphe est-il connexe ? Justifier.
Le cycle E - F - G - J - N - M - L - K - I - H - E contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets, il existe une chaîne les reliant. Donc le graphe est connexe.
Antoine prétend avoir trouvé un itinéraire permettant d'emprunter chaque allée une et une seule fois mais Louisa lui répond que c'est impossible.
Lequel des deux a raison ? Justifier la réponse.
Il y a six sommets de degré impair, les sommets E, F, G ,K, L et N donc il n'existe pas de chaîne eulérienne. Par conséquent, Louisa a raison.
On considère la matrice M ci-dessous (a, b et c sont des entiers).
Déterminer les entiers a, b et c pour que la matrice M représente la matrice d'adjacence associée au graphe Γ, les sommets étant pris dans l'ordre alphabétique.
La matrice d'adjacence associée au graphe Γ est .
Soit S la matrice définie par : . On admet que : et
Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant F à L. Préciser ces chemins.
Le coefficient de la matrice situé à l'intersection de la deuxième ligne et de la huitième colonne est égal à 4. Il y a quatre chemins de longueur 3 reliant F à L : F - E - H - L, F - G - H - L, F - G - M - L et F - J - M - L.
Déterminer, en justifiant, le nombre de chemins de longueur 3 partant de E.
La somme des coefficients de la première ligne de la matrice est égale à 43. Il y a 43 chemins de longueur 3 partant de E.
Que signifie le coefficient à l'intersection de la première ligne et de la troisième colonne de S ?
Il y a 11 chemins de longueur 1, 2 ou 3 reliant E à G.
Un défilé part tous les jours à 14 h du sommet N. Louisa et Antoine choisissent de déjeuner dans un restaurant situé au sommet E avant d'aller admirer le défilé.
À l'aide d'un algorithme, déterminer le chemin que doivent emprunter Louisa et Antoine pour se rendre du restaurant au départ du défilé le plus rapidement.
Déterminons le chemin que doivent emprunter Louisa et Antoine pour se rendre du restaurant au départ du défilé le plus rapidement à l'aide de l'algorithme de Dijkstra.
| E | F | G | H | I | J | K | L | M | N | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | E (0) |
| 5 (E) | 3 (E) | 6 (E) | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | G (3) | |
| 5 (E) | 5 (G) | ∞ | 9 (G) | ∞ | ∞ | 11 (G) | ∞ | F (5) | ||
| 5 (G) | ∞ | 9 (G) | ∞ | ∞ | 11 (G) | ∞ | H (5) | |||
| 12 (H) | 9 (G) | ∞ | 9 (H) | 11 (G) | ∞ | J (9) | ||||
| 12 (H) | ∞ | 9 (H) | 11 (G) | 17 (J) | L (9) | |||||
| 12 (H) | 15 (L) | 10 (L) | 17 (J) | M (10) | ||||||
| 12 (H) | 15 (L) | 15 (M) | I (12) | |||||||
| 15 (L) | 15 (M) | K (15) | ||||||||
| 15 (M) | N (16) |
Le sommet N étant marqué, pour lire la chaîne de poids minimal, on part de N et on "remonte" la chaîne en suivant les prédécesseurs. .
Le chemin le plus rapide pour se rendre du restaurant au départ du défilé est E - G - H - L - M - N pour une durée de 15 minutes.
À quelle heure au plus tard doivent-ils quitter le restaurant pour assister au début du défilé ?
La durée du trajet le plus rapide étant de 15 minutes, Louisa et Antoine devront quitter le restaurant au plus tard à 13 h 45.
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.