View
107
Download
0
Category
Preview:
Citation preview
IN302 – Chapitre 4
Flotset réseaux de transport
Réseaux de transport
Réseau de transport
S
b
a
P
10
40 30
10
20
Flot ?
S
b
a
P
10
40 30
10
20S
b
a
P
20
20 20
20
10
Flot ?
S
b
a
P
10
40 30
10
20S
b
a
P
20
20 20
20
10
Flot ?
S
b
a
P
10
40 30
10
20S
b
a
P
20
20 30
10
10
Flot
S
b
a
P
10
40 30
10
20S
b
a
P
20
20 30
10
10
40
Flot compatible
S
b
a
P
10
40 30
10
20S
b
a
P
10
20 30
0
10
30
Flot compatible
S
b
a
P
10
40 30
10
20S
b
a
P
10
20 30
0
10
30
Ce flot est-il maximal ?
Flot compatible maximal
S
b
a
P
10
40 30
10
20S
b
a
P
10
30 30
10
0
40
Réseau d’écart
S
b
a
P
10
40 30
10
20S
b
a
P
10
20 30
0
10
30
S
b
a
P
20
10
10
Réseau d’écart
S
b
a
P
10
40 30
10
20S
b
a
P
10
20 30
0
10
30
S
b
a
P
20
10
10
10
2030
10
Ford & Fulkerson
S
b
a
P
10
40 30
10
20S
b
a
P
0
0 0
0
0
0
40
10
20S
b
a
P
10
30
20
10
30 min(10, 20, 30) = 10
0
0
0
0
Ford & Fulkerson
S
b
a
P
10
40 30
10
20S
b
a
P
10
0 10
0
10
10
S
b
a
P
40
10
20
10
30 min(10, 20, 30) = 10
Ford & Fulkerson
S
b
a
P
10
40 30
10
20S
b
a
P
10
0 10
0
10
10
S
b
a
P
40
10
10
20
10
10
10
Ford & Fulkerson
S
b
a
P
10
40 30
10
20S
b
a
P
10
0 10
0
10
10
S
b
a
P
40
10
10
20
10
10
10
40 20 min(40, 20) = 20
20 30
30
Ford & Fulkerson
S
b
a
P
10
40 30
10
20S
b
a
P
10
20 30
0
10
30
S
b
a
P
20
10
10 10
30
10
20
Ford & Fulkerson
S
b
a
P
10
40 30
10
20S
b
a
P
10
20 30
0
10
30
S
b
a
P
20
10
10 10
30
10
20
20
10
10
min(20, 10, 10) = 10
30
0
10
40
Ford & Fulkerson
S
b
a
P
10
40 30
10
20S
b
a
P
10
30 30
10
0
40
S
b
a
P
10
20
30
10
30
10
Flot maximal / coupe minimale
S
b
a
P
c
d
e
f
82
3
16
6
5
3
4
7
117
6
5
6
Flot maximal / coupe minimale
S
b
a
P
c
d
e
f
5/82/2
3/3
1/16/6
6/6
5/5
3/3
3/4
4/7
11/116/7
4/6
3/5
6/6
27
21
Flot maximal / coupe minimale
S
b
a
P
c
d
e
f
5/82/2
3/3
1/16/6
6/6
5/5
3/3
3/4
4/7
11/116/7
4/6
3/5
6/6
24
21
Flot maximal / coupe minimale
S
b
a
P
c
d
e
f
5/82/2
3/3
1/16/6
6/6
5/5
3/3
3/4
4/7
11/116/7
4/6
3/5
6/6
26
21
Flot maximal / coupe minimale
S
b
a
P
c
d
e
f
5/82/2
3/3
1/16/6
6/6
5/5
3/3
3/4
4/7
11/116/7
4/6
3/5
6/6
21
21
Coupes minimales (graph cuts)
Trucages photo et video
Génération de textures
Inpainting (restauration)
Segmentation d’images 2D et 3D
Reconstruction de formes 3D
Stéréovision
Recommended