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.
Ce graphe admet-il un cycle eulérien ? (La réponse devra être justifiée). Si oui donner un tel cycle.
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 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.
Quelle est la longueur en minutes de ce chemin ? Arthur sera-t-il en 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.