Newer
Older
## Flots en bois
### 1. Test sur algorithme MaxFlow
Le test sur l'algorithme MaxFlow nous retourne l'image du graphe suivant:
Il sort en s = 15 et rentre en t 15. Le flot maximal est **15**
En appliquant cet algorithme sur un autre exemple on obtient de même commet flot maximale entrant dans t = 10:
Ce qui valide le contrainte de conservation des flots.
### 2. Test sur l'algorithme de transport de grumes
#### Modèle de représentation
Nous allons maintenant tester notre algorithme sur l'exercice de transport de grumes disponible sur ce [lien](https://eureka.univ-lehavre.fr/pluginfile.php/141682/mod_assign/introattachment/0/TP1_flot_boise.pdf?forcedownload=1).
Afin de modéliser notre graphe,nous allons nous inspirer de ce modèle:
* Les rivières représentent les arcs
* Les sommets representent la jonction de rivières et sera noté par la concaténation de leur noms sauf pour les s, t et les scierie de départ.
#### Calcul des capacités
Les capacités du réseaux d les sommets sont dupliqué en sommet entrant et sommet sortant avec un arc les reliant. La capacité de cet arc est égale à la capacité du sommet.e transport de grumes sont représentées dans le tableau suivant:
| A |B |C |D |E |F |G |H |I |J |K |L |M |N |O |P |Q |R |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|10 |12 |15 |10 |15 | 22 |10 |5 |25 |32 |30 |15 |10 |10 |5 |40 |20 |20 |
**Remarques**
- Les coupes 1 et 2 déversent toutes les deux dans la rivière A, on peut les confondre en un seul noeud.
- Nous allons faire quelques calculs puisque chaque jonctions de rivières, la capacité résultante est la somme des capacités entrantes.
- La rivière O n'a aucune scierie sur ces berges mais départage seulement la capacité de la rivière L avec N, donc dans ce cas, on n'aura pas besoin de l'afficher dans le graphe.
- α et β sont toutes les deux situées sur la rivière N donc on peut les unir en un seul noeud.
- La rivière E s'ajoute à la rivière D pour former la rivière I mais ne prend pas source dans s, alors on peut simplement attribuer à la rivière I la somme des capacités entrantes dans DEI
Ainsi nous obtenons la figure ci-dessous:
Nous obtenons dans le console une valeur de flot maximisé de 35.0. C'est à dire que le nombre maximale de grumes pouvant circuler dans notre réseau de rivères ne pourra dépasser cette valeur.
On obtient aussi des s-t coupes correspondantes.
### Ajout des capacités de traitement pour les scieries
Dans le cas où on ajoutera des capacités aux scieries, les sommets sont dupliqué en sommet entrant et sommet sortant avec un arc les reliant. La capacité de cet arc est égale à la capacité du sommet. Le chemin emprunté pour le transport de flux vers t changera selon la figure suivante:
La valeur du flot maximal sera de **34**.