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
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
 
      A---B
     /|     |\
  s   |     | T
    \ |     | /
      C---D
Les coupes suivantes sont elles valables et donc minimale ?
(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