Les parties A et B peuvent être traitées indépendamment l'une de l'autre
On considère le graphe Γ ci-dessous :
Ce graphe admet-il une chaîne eulérienne ? (La réponse devra être justifiée). Si oui donner une telle chaîne.
La chaîne W-O-P-E-T-H-L passe par tous les sommets du graphe. Donc le graphe Γ est connexe.
D'autre part les degrés des sommets sont :
| Sommets | E | H | L | O | P | T | W |
| Degrés | 2 | 3 | 4 | 2 | 4 | 4 | 3 |
Le graphe Γ est connexe et contient deux sommets de degré impair il admet donc une chaîne eulérienne par exemple H-T-E-P-L-T-P-O-W-L-H-W.
Ce graphe admet-il un cycle eulérien ? (La réponse devra être justifiée). Si oui donner un tel cycle.
Le graphe Γ contient deux sommets de degré impair il n'admet pas de cycle eulérien.
Donner la matrice M associée au graphe Γ (les sommets seront pris dans l'ordre alphabétique : E ; H ; L ; O ; P ; T ; W).
La matrice M associée au graphe Γ est
La classe de Terminale d'Arthur est en voyage scolaire en Angleterre.
Les professeurs organisateurs de ce voyage décident de visiter plusieurs sites de Londres.
Les sites retenus dans Londres sont les suivants : Warren Street, Oxford Circus, Piccadilly Circus, Leicester Square, Holborn, Embankment et Temple. Ces lieux sont désignés respectivement par les lettres W, O, P, L, H, E et T et sont représentés dans le graphe Γ donné ci-dessus (chaque sommet représente un site à visiter et chaque arête une route reliant deux sites).
Les élèves sont laissés en autonomie deux heures pour faire du shopping et ramener des souvenirs à leurs familles. Le point de rendez-vous avec les organisateurs est fixé à Temple. Les temps de parcours en minutes entre chaque sommet ont été ajoutés sur le graphe.
Arthur, qui est à Oxford Circus, n'a pas vu le temps passer. Lorsqu'il s'en rend compte, il ne lui reste plus que 40 minutes pour arriver à Temple.
Déterminer le plus court chemin en minutes reliant Oxford Circus à Temple. Justifier la réponse à l'aide d'un algorithme.
Pour déterminer le trajet le plus court pour aller de O à T, on utilise l'algorithme de Dijkstra.
| O | P | W | E | L | H | T | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | O (0) |
| 13 (O) | 15 (O) | ∞ | ∞ | ∞ | ∞ | P (13) | |
| 15(O) | 28 (P) | 18 (P) | ∞ | 47 (P) | W (15) | ||
| 28 (P) | 18 (P) | 29 (W) | 47 (P) | L (18) | |||
| 28 (P) | 26 (L) | 47 (P) | H (26) | ||||
| 28 (P) | 46 (H) | E (28) | |||||
| 46 (H) | T (46) |
Le sommet T étant marqué, pour lire la chaîne de poids minimal, on part de T et on "remonte" la chaîne en suivant les prédécesseurs. .
Le plus court chemin en minutes reliant Oxford Circus à Temple est Oxford Circus-Piccadilly Circus-Leicester Square-Holborn-Temple
Quelle est la longueur en minutes de ce chemin ? Arthur sera-t-il en retard ?
La durée du trajet est de 46 minutes. Donc Arthur sera en retard. (Mais rien ne l'empêche de courir pour rattraper son retard ...)
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.