Les parties A et B sont indépendantes
L'objet d'étude est le réseau des égouts d'une ville. Ce réseau est modélisé par le graphe ci-dessous : les sommets représentent les stations et les arêtes, les canalisations.
Ce graphe admet-il une chaîne eulérienne ?
Quel est le nombre de sommets de degré impair ?
Justifier que le nombre chromatique de ce graphe est compris entre 4 et 6.
Le graphe pondéré ci-dessus donne, en minutes, les durées des trajets existant entre les différentes stations du réseau des égouts.
Un ouvrier doit se rendre par ce réseau de la station E à la station S. Déterminer, en utilisant un algorithme, le trajet le plus rapide pour aller de E à S et préciser sa durée.
Algorithme de Dijkstra.
Ayant choisi le trajet le plus rapide, l'ouvrier arrivant en C, apprend que les canalisations CG et CS sont fermées pour cause de travaux et qu'il ne peut les utiliser.
Peut-il terminer, au plus vite, son trajet jusqu'à S ? Combien de temps le trajet entre E et S prendra-t-il dans ce cas ?
S'il avait su dès le départ que les canalisations CG et CS étaient impraticables, quel trajet aurait choisi l'ouvrier pour se rendre, au plus vite de E à S ? Combien de temps ce trajet aurait-il pris ?
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.