Bonjour,
j'ai remarqué sur le cours "graphes et algorithmies" ->
ftp://ftp-developpez.com/lapoire/alg...ue/graphes.pdf
à la page 78, que la coupe minimale concernant la figure 10.1 est désignée par :
{a,b,d} et {e,c,f}, mais je ne vois pas pourquoi on choisit cela,
pourquoi ne pas prendre par ex {a,b,d,e} {c,f} ?
De plus je vois cette propriété partout : Pour tout réseau, la valeur maximal des flots est égale à la capacité minimale des coupes.
Donc, prenons un graphe dans lequel on a déjà évalué ce flot maximal
avec la notation suivante : p
Les coupes suivantes sont elles valables et donc minimale ?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 A---B /| |\ s | | T \ | | / C---D
(A-B) (C-D)
(B-T)(T-D)
(B-T)(B-D)(C-D)
et pourquoi pas
(S-A)(A-C)(C-D)
(S-A)(S-C)
Merci
Partager