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.
1. Ce graphe admet-il une chaîne eulérienne ?
2. Justifier que le nombre chromatique de ce graphe est compris entre 4 et 6 (...)
[...] Exercice type Bac de mathématiques Centres Etrangers (juin 2007) 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. Partie A 1. Ce graphe admet-il une chaîne eulérienne ? 2. Justifier que le nombre chromatique de ce graphe est compris entre 4 et 6. Partie B 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. [...]
[...] Combien de temps le trajet entre E et S prendra-t-il dans ce cas ? B. 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 ? Partie A 1. Ce graphe admet-il une chaîne eulérienne ? Pour qu'il y ait chaine eulérienne il faut que le nombre de sommets de degré impair soit inférieur ou égal à deux, or il y en a quatre G et S). [...]
[...] Le nombre chromatique de ce graphe est bien compris entre 4 et 6 [...]
Source aux normes APA
Pour votre bibliographieLecture en ligne
avec notre liseuse dédiée !Contenu vérifié
par notre comité de lecture