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