Problèmes de flots
217
: ensemble des sommets destinations marqués,
: ensemble des sommets destinations non marqués.
On a symbolisé ci-dessus la coupe de capacité minimale. On a alors les propriétés
suivantes qui découlent de l'algorithme de Ford-Fulkerson :
Les arcs
sont saturés,
Les arcs
sont saturés,
Les arcs
sont de flot nul.
Quant aux arcs
, ils ne peuvent pas exister, puisqu'ils sont de capacité infinie et
qu'ils appartiennent à
, étant la coupe ( ou encore si un arc
existait, comme
il est de capacité infinie et que le sommet de
est marqué, alors le sommet de
serait
marqué.)
Opérons alors sur la fonction potentiel la transformation suivante :
On obtient une nouvelle fonction potentiel . En effet, on a évidemment (
1
X
x i
ij
j
i
j
'
i
'
j
c
Y
y
=
1
2
X
x i
ij
j
i
j
'
i
'
j
c
Y
y
=
2
2
X
x i
ij
j
i
j
'
i
'
j
c
Y
y
1
=
1
1
X
x i
ij
j
i
j
'
i
'
j
c
Y
y
1
=
2
(puisque, pour ce dernier cas, la non-existence des arcs
signifie
Calculons alors la fonction
.
X 1
X 2
Y 1
Y 2
x 0
z
0
Coupe de capacité minimale
Sommets marqués
Sommets non marqués