# FlowBB

## Construction du graphe

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;">
    <img src="./data/bettergraph.png" />
</div>

<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.