Solutions
472
Essayons alors d’affec ter le maxi mum
de zéros. On obtient le tableau 2.
Avant de conti nuer à appli quer l’algo -
rithme hon grois, il faut véri fier que l’on
a bien obtenu un cou plage maximal.
À cet effet, on peut éta blir un réseau
de tran sport, dont la capa cité de tout
arc est 1.
On constate que la pro cé dure
de mar quage échoue ; on a donc un
flot maximal et, par tant, un cou -
plage maximal. Dans ces condi tions,
on applique à la matrice pré cé dente
l’algo rithme hon grois. On marque les
lignes Ε et F, ce qui conduit à mar quer
ensuite la colonne a, puis la ligne A.
On raye alors les lignes non marquées B,
C, D et la colonne marquée a (tab. 2 bis). Le
plus petit élé ment du tableau res tant est 4 ; on
l’enlève à tous les élé ments de ce tableau res -
tant et on l’ajoute aux élé ments rayés deux
fois (Tab. 3).
On fait ainsi appa raître un nou veau zéro
(ligne A, colonne d ) mais l’affec ta tion reste
la même ; il est facile de véri fier que le cou -
plage est encore maximal ; le som met d de la
deuxième colonne du réseau de tran sport peut
être mar qué +A, le som met c de la pre mière
colonne, –D, mais le mar quage s’arrête là :
�0
�a
�A
�d
�
0
E
S
�E (ou � F)
a
d
f
e
b
c
F
A
C
B
D
Graphe associé au tableau 3
Graphe associé au tableau 2
sur les arcs gras le flux vaut 1 (0 sur les maigres)
tableau 3
A
B
C
D
E
F
0
0
0
60
66
0
14
77
52
7
7
44
51
51
57
68
38
15
0
13
3
20
19
56
59 25
44






61
68
12
33
0
0
0
0
0
a
b
c
d
e
f
tableau 2 bis
A
B
C
D
E
F
0
0
0
60
66
0
18
77
56
11
11
48
55
55
57
68
42
19
4
17
3
16
15
52
63 29
48
61
72
12
33
0
0
0
0
0
a
b
c
d
e
f
�
�
�
�