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 ?
Les degrés des différents sommets sont :
Sommets | A | B | C | D | E | G | S |
Degrés | 4 | 4 | 5 | 5 | 2 | 3 | 3 |
Il y a 4 sommets de degré impair C, D, G et S.
Le nombre de sommets de degré impair est supérieur à deux donc il n'existe pas de chaîne eulérienne.
Justifier que le nombre chromatique de ce graphe est compris entre 4 et 6.
Soit γ le nombre chromatique de ce graphe.
Le plus haut degré des sommets est 5 donc .
est un sous graphe complet d'ordre 4 alors .
Ainsi, 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.
Pour déterminer le plus court chemin possible pour aller de la station E à la station S on utilise l'algorithme de Dijkstra.
E | A | B | C | D | G | S | Sommet sélectionné et commentaires |
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | E de poids 0 on marque les sommets adjacents A et B |
4 (E) | 7 (E) | ∞ | ∞ | ∞ | ∞ | A on marque les sommets adjacents B (4+2<7), C (12 =4+8) et D (13 =5+8) | |
6 (A) | 12 (A) | 13 (A) | ∞ | ∞ | B on marque les sommets adjacents C (6+5<12) et D (6+6<13) | ||
11 (B) | 12 (B) | ∞ | ∞ | C (11+3>12 on conserve le poids de D ) et on marque les sommets G et S | |||
12 (B) | 15 (C) | 19 (C) | D (12+5>15 on conserve le poids de G ) et (12+8>20 on conserve le poids de S ) | ||||
15 (C) | 19 (C) | G (15+5>19 on conserve le poids de S ) | |||||
19 (C) | S |
Pour déterminer le trajet le plus rapide on remonte les sommets à l'envers :
S vient de C qui vient de B qui vient de A qui vient de E.
Le trajet le plus rapide est E-A-B-C-S, il dure 19 minutes.
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 ?
Arrivé en C, l'ouvrier doit pour terminer son trajet utiliser la canalisation DS. Or le trajet le plus rapide pour atteindre la station D en partant de C est celui qui utilise la canalisation CD.
Le temps du trajet utilisé pour arriver en C est de 11 minutes. Soit une durée totale exprimée en minutes de
Le nouveau trajet est E-A-B-C-D-S, il dure 22 minutes.
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 ?
L'algorithme de Dijkstra appliqué au graphe ci-dessous permet de déterminer le plus court chemin possible pour aller de la station E à la station S.
E | A | B | C | D | G | S |
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
4 (E) | 7 (E) | ∞ | ∞ | ∞ | ∞ | |
6 (A) | 12 (A) | 13 (A) | ∞ | ∞ | ||
11 (B) | 12 (B) | ∞ | ∞ | |||
12 (B) | ∞ | ∞ | ||||
17 (D) | 20 (D) | |||||
20 (D) |
Les canalisations CG et CS étant impraticables, le trajet le plus rapide pour arriver en S passe par D en venant de B.
Le trajet le plus rapide est donc E-A-B-D-S, il dure 20 minutes.
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.