Coupe minimale/flot maximal

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
http://upload.wikimedia.org/wikipedi...x_flow.svg.png

avec la notation suivante : p

Code:

---

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

Citation:

---

Envoyé par mensoif

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} ?

---

Et bien parce que la capacité de la coupe BC+EF vaut 6, alors que celle de la coupe DE+BE+BC vaut 5.

Citation:

---

De plus je vois cette propriété partout : Pour tout réseau, la valeur maximal des flots est égale à la capacité minimale des coupes.

---

Une manière plus physique de voir les choses :

Le débit maximal dans un réseau de tuyaux est égal à la somme des débits dans ses goulets d'étranglement.

Si on veut augmenter le débit maximal, on n'a pas d'autre choix que d'augmenter la capacité d'un de ces goulets (puisque ce sont eux qui empechent d'avoir plus de débit).

Citation:

---

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

---

Elles sont toutes valides (elles séparent le graphe en 2) mais elles ne sont pas toutes minimales

AB+CD = 5
BT+TD = 5
BT+BD+CD = 9
SA+AC+CD = 7
SA+SC = 6

Comme on s'en doutait, ce sont les tuyaux qui sont les goulets d'étranglement (flot=capacité) qui forment la coupe minimale.

pseudocode a encore frappé ! merci à toi ! :ave:

Citation:

---

Envoyé par mensoif

pseudocode a encore frappé ! merci à toi ! :ave:

---

Là ça va, ce n'était pas trop dur. :P