Les parties A et B peuvent être traitées indépendamment
On considère le graphe Γ ci-dessous :
Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui donner une telle chaîne.
Ce graphe admet-il un cycle eulérien ? Justifier la réponse. Si oui donner un tel cycle.
Donner la matrice M associée au graphe Γ. Les sommets seront pris dans l'ordre alphabétique : A, B, C, D, E, F, G.
Une région est munie d'un réseau de trains, représenté par le graphe Γ ci-dessous.
Les stations sont symbolisées par les sommets A, B, C, D, E, F et G. Chaque arête représente une ligne reliant deux gares. Les temps de parcours (correspondance comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe.
Déterminer le plus court chemin en minutes, reliant la gare B à la gare G. Justifier la réponse grâce à un algorithme.
Pour déterminer le trajet le plus court reliant la gare B à la gare G, on utilise l'algorithme de Dijkstra.
Quelle est la longueur en minutes de ce chemin ?
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.