232
Recherche opérationnelle
Par rapport au graphe précédent, l'addition d'un arc
aura pour effet :
- soit d'augmenter le couplage si le sommet
n'était pas saturé dans le
couplage précédent.
- soit d'augmenter le nombre de sommets de , dans le cas contraire : en effet, le
sommet de l'arc ajouté appartenant à devient alors marqué, et doit être ajouté
à ; par ailleurs, certains arcs
peuvent disparaître, mais comme ils
n'étaient pas saturés dans le couplage précédent, ce ne sont pas eux qui avaient
entraîné le marquage des sommets de , qui restent marqués.
En conséquence, soit le couplage augmente, soit l'ensemble possède plus de sommets
qu'auparavant.
Mais alors, dans le second cas, comme la taille du couplage n'est pas encore celle que
l'on recherche, c'est-à-dire , il existe des arcs
non saturés et au bout d'un certain
temps d'opérations analogues (addition d'arc
), comme augmente, on réussira
à marquer et donc à augmenter le couplage.
On voit ainsi (sans que ce qui précède constitue une démonstration) que le processus est
convergent et qu'on aboutira au bout d'un nombre fini d'étapes à un couplage de zéros de
taille égale à (ici 6).
Pratiquement, il n'est pas commode de changer l'ordre des rangées de la matrice des
coûts. Pour constituer les différents tableaux
considérés ci-dessus, on procède de
la façon suivante:
Sur la matrice 3, où les zéros du couplage maximal sont encadrés, les autres barrés,
a) on marque toute ligne n'ayant pas de zéro encadré (ces lignes correspondent à des
sommets insaturés de , donc à des sommets de ).
b) on marque toute colonne ayant un zéro barré dans une ligne marquée (la ligne étant
marquée correspond à un sommet marqué; l'existence d'un zéro barré dans la colonne
envisagée signifie l'existence d'un arc de flot nul entre le sommet marqué associé à la
ligne et le sommet associé à la colonne; on peut donc marquer ce dernier).
c) on marque toute ligne ayant un zéro encadré sur une colonne marquée (existence d'un
arc de flot non nul entre un sommet de
et un sommet de , donc marquage du
sommet de ).
d) on revient en b).
Après épuisement de cette procédure, les lignes marquées correspondent à
et les
colonnes marquées à .
Recherche opérationnelle
Par rapport au graphe précédent, l'addition d'un arc
aura pour effet :
- soit d'augmenter le couplage si le sommet
n'était pas saturé dans le
couplage précédent.
- soit d'augmenter le nombre de sommets de , dans le cas contraire : en effet, le
sommet de l'arc ajouté appartenant à devient alors marqué, et doit être ajouté
à ; par ailleurs, certains arcs
peuvent disparaître, mais comme ils
n'étaient pas saturés dans le couplage précédent, ce ne sont pas eux qui avaient
entraîné le marquage des sommets de , qui restent marqués.
En conséquence, soit le couplage augmente, soit l'ensemble possède plus de sommets
qu'auparavant.
Mais alors, dans le second cas, comme la taille du couplage n'est pas encore celle que
l'on recherche, c'est-à-dire , il existe des arcs
non saturés et au bout d'un certain
temps d'opérations analogues (addition d'arc
), comme augmente, on réussira
à marquer et donc à augmenter le couplage.
On voit ainsi (sans que ce qui précède constitue une démonstration) que le processus est
convergent et qu'on aboutira au bout d'un nombre fini d'étapes à un couplage de zéros de
taille égale à (ici 6).
Pratiquement, il n'est pas commode de changer l'ordre des rangées de la matrice des
coûts. Pour constituer les différents tableaux
considérés ci-dessus, on procède de
la façon suivante:
Sur la matrice 3, où les zéros du couplage maximal sont encadrés, les autres barrés,
a) on marque toute ligne n'ayant pas de zéro encadré (ces lignes correspondent à des
sommets insaturés de , donc à des sommets de ).
b) on marque toute colonne ayant un zéro barré dans une ligne marquée (la ligne étant
marquée correspond à un sommet marqué; l'existence d'un zéro barré dans la colonne
envisagée signifie l'existence d'un arc de flot nul entre le sommet marqué associé à la
ligne et le sommet associé à la colonne; on peut donc marquer ce dernier).
c) on marque toute ligne ayant un zéro encadré sur une colonne marquée (existence d'un
arc de flot non nul entre un sommet de
et un sommet de , donc marquage du
sommet de ).
d) on revient en b).
Après épuisement de cette procédure, les lignes marquées correspondent à
et les
colonnes marquées à .