Chapitre *** TD Yassine Hacha¨ ıchi Th´ eorie des graphes et applications Exerc

Chapitre *** TD Yassine Hacha¨ ıchi Th´ eorie des graphes et applications Exercice 1. On se propose de relier par un r´ eseau de fibres optiques les villes a, b, c, d, e, f. Les chemins possibles (en fonction de la nature du terrain) sont donn´ ees par le graphe : a b d c f e ❅ ❅ ❅ ❅ ❅ ❅ ✁ ✁ ✁ ✁ ✁ ✁ Le coˆ ut (en millier de dinars) du cablage de chaque liaison possible est : γ(a, b) = 4 γ(a, e) = 6 γ(a, f) = 5 γ(b, c) = 4 γ(b, d) = 2 γ(b, f) = 2 γ(c, d) = 8 γ(c, f) = 1 γ(d, e) = 2 γ(e, f) = 1 1- Donnez un r´ eseau qui connecte toutes les villes de coˆ ut minimal (par l’algorithme de Prim ou de Kruskal). 2- Donnez le coˆ ut minimal de connexion des villes (d, f) (par la m´ ethode de Dijkstra). Exercice 2. On consid` ere 4 villages V1, V2, V3 et V4 qui sont aliment´ es par 3 chateaux d’eau C1, C2 et C3. Ces derniers ont des d´ ebits respectifs (en litres par seconde) de 45, 25 et 20. Les besoins respectifs en eau des villages sont 30, 10, 20 et 30 litres/secondes. On donne ci-dessous les capacit´ es des diff´ erentes canalisations qui relient les chateaux d’eau aux villages. (C1, V1) : 10; (C1, V2) : 15; (C1, V4) : 20; (C2, V1) : 20 (C2, V2) : 5; (C2, V3) : 15; (C3, V3) : 10; (C3, V4) : 10 D´ eterminer le meilleur plan d’alimentation des quatre villages. Exercice 3. Donnez le flot maximum du r´ eseau suivant : 1 2 uploads/Geographie/ enicar.pdf

Tags
Administrationexercice eseau villes donnez minimal
Documents similaires
  • 35
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager