Newer
Older
Fichier DGS réseau routier:
```txt
DGS004
roadgraph 23 0
an A x:0 y:1
an B x:1 y:2
an C x:1 y:0
an D x:4 y:2
an E x:2 y:1
an F x:4 y:0
an G x:5 y:2
an H x:5 y:0
an I x:6 y:1
ae AB A > B c:800
ae AC A > C c:700
ae BD B > D c:600
ae BE B > E c:100
ae CD C > D c:100
ae CE C > E c:300
ae CF C > F c:100
ae DG D > G c:700
ae DH D > H c:200
ae EG E > G c:500
ae FG F > G c:200
ae FH F > H c:400
ae GI G > I c:500
ae HI H > I c:900
```
## Question 1 : Mettre en avant le flot maximum du réseau
<div style="display:flex;justify-content:center;">
<em style="display:flex;justify-content:center;">Visualisation du graphe, avec flots affichés et arcs saturés en rouge</em>
Le débit horaire total maximal de véhicules susceptibles de s'écouler des villes A à I (flot maximal du réseau) est de 800.\
Cette réponse est mise en avant par la visualisation précédente (arcs saturés).\
De plus, la coupe `{A, B, C, D, E, G}` a une capacité de 800, ce qui indiquait que la valeur F du flot maximal ne pouvait être supérieure.
## Question 2 : Le problème des tronçons d'autoroute
Avant toute chose, on peut remarquer que le réseau est très inégal en termes de capacités de flot ;
certains arcs possèdent 9 fois plus de volume que d'autre/
\
Afin de résoudre ce problème de tronçons d'autoroutes, il suffit de trouver la coupe ayant la capacité minimale et de construire le tronçon sur l'arc de la coupe appartenant à la route sélectionnée. Ainsi, nous obtiendrons la construction la plus efficace (car l'on remplace les arcs les moins "performants").\
Voici les évolutions simulées après chaque construction de tronçons d'autoroutes:
|Ordre|Tronçon|Nouveau flot maximal|
|-----|-------|--------------------|
|1 |DH |1200 |
|2 |CD |1400 |
|3 |AC |1400 |
|4 |HI |3000 |
On remarque qu'après avoir construit la 3ème autoroute le flot maximal ne change pas : c'est parce qu'à ce moment, peu importe la route choisie, le flot maximal ne peut augmenter.