Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
142
les som mets x tels qu’il existe un arc (x, y) de flux non nul (donc ici saturé puisque tous
les arcs ont pour capa cité 1), si y est déjà mar qué ; ici on a mar qué – le som met A.
Cette cor res pon dance est détaillée plus bas : sur les graphes des figures 4.33
et 4.34.
Tra çons alors un trait sur les lignes non mar -
quées et les colonnes mar quées (tableau 4.6). Le
sous- tableau res tant com prend les cases asso -
ciées aux arcs « utiles » c’est- à-dire tels que, si
l’un d’eux était ajouté au graphe pré cé dent, on
pour rait mar quer de nou veaux som mets. Consi -
dé rons le plus petit nombre du tableau res tant :
retranchons- le de tous les élé ments non rayés et
ajoutons- les aux élé ments rayés deux fois (tableau
4.7). Cela revient à ajou ter au graphe le (ou les)
arc(s) « utile(s) » de plus faible coût : il y a en
quatre ici, ceux de coût 1 (tableau 4.6), dans le
tableau res tant. On obtient alors le tableau 4.7.
Sur le tableau 4.7, il est main te nant pos sible
d’affec ter un zéro par ligne par colonne, et cela
de trois manières dif fé rentes qui consti tuent les
solu tions équi va lentes du pro blème, en ce sens
qu’elles donnent toutes, en reve nant au tableau
4.1, la somme (coût) 10.
On remar quera que le coût de 10 cor res pond
bien à la somme de la borne infé rieure 9 trou vée pré -
cé dem ment, et du plus petit élé ment sous trait pos -
té rieu re ment au tableau. Plus géné ra le ment, soit g
la borne du coût lors d’une itération quel conque ;
notons X M les som mets mar qués du pre mier niveau et Y M , ceux du second niveau.
On montre que la borne infé rieure du coût passe de g à g 1 a (Card X M 2 Card Y M )
où a est le plus petit coût du « tableau res tant », c’est- à-dire du sous- tableau dont les
lignes sont mar quées (X M ) et dont les colonnes ne sont pas mar quées (Y M ) ; le lec teur
pourra prou ver que nécessairement on a : Card X M . Card Y M .
Au cas où le Tableau 4.7 n’aurait pas fourni la solu tion, il aurait fallu reprendre l’algo -
rithme, après avoir affecté le plus pos sible de zéros, (ce que l’on véri fie en résol vant un
pro blème de flot maximal comme ci dessus), à la pro cé dure de mar quage, et ainsi de
suite jus qu’à l’obten tion de la solu tion (qui nécessite en général plusieurs itérations).
Une solu tion opti male consiste à affec ter : A à a ; B à e ; C à c ; D à b et Ε à d. Elle
a pour coût 10.
Telle est la méthode hon groise, à laquelle on a donné ce nom en sou ve nir de deux
mathéma ti ciens hon grois, Egervary et König, qui ont contri bué, avec Kuhn, à en
fon der la théo rie.
Tableau 4.6
A
B
C
D
E
a b c d e
0 1 2 1 2
0 3 1 2 0
2 1 0 2 1
0 1 2 2 1
1 0 3 0 2
Tableau 4.7
A
B
C
D
E
a b c d e
0 0 1 0 1
1 3 1 2 0
3 1 0 2 1
0 0 1 1 0
2 0 3 0 2
142
les som mets x tels qu’il existe un arc (x, y) de flux non nul (donc ici saturé puisque tous
les arcs ont pour capa cité 1), si y est déjà mar qué ; ici on a mar qué – le som met A.
Cette cor res pon dance est détaillée plus bas : sur les graphes des figures 4.33
et 4.34.
Tra çons alors un trait sur les lignes non mar -
quées et les colonnes mar quées (tableau 4.6). Le
sous- tableau res tant com prend les cases asso -
ciées aux arcs « utiles » c’est- à-dire tels que, si
l’un d’eux était ajouté au graphe pré cé dent, on
pour rait mar quer de nou veaux som mets. Consi -
dé rons le plus petit nombre du tableau res tant :
retranchons- le de tous les élé ments non rayés et
ajoutons- les aux élé ments rayés deux fois (tableau
4.7). Cela revient à ajou ter au graphe le (ou les)
arc(s) « utile(s) » de plus faible coût : il y a en
quatre ici, ceux de coût 1 (tableau 4.6), dans le
tableau res tant. On obtient alors le tableau 4.7.
Sur le tableau 4.7, il est main te nant pos sible
d’affec ter un zéro par ligne par colonne, et cela
de trois manières dif fé rentes qui consti tuent les
solu tions équi va lentes du pro blème, en ce sens
qu’elles donnent toutes, en reve nant au tableau
4.1, la somme (coût) 10.
On remar quera que le coût de 10 cor res pond
bien à la somme de la borne infé rieure 9 trou vée pré -
cé dem ment, et du plus petit élé ment sous trait pos -
té rieu re ment au tableau. Plus géné ra le ment, soit g
la borne du coût lors d’une itération quel conque ;
notons X M les som mets mar qués du pre mier niveau et Y M , ceux du second niveau.
On montre que la borne infé rieure du coût passe de g à g 1 a (Card X M 2 Card Y M )
où a est le plus petit coût du « tableau res tant », c’est- à-dire du sous- tableau dont les
lignes sont mar quées (X M ) et dont les colonnes ne sont pas mar quées (Y M ) ; le lec teur
pourra prou ver que nécessairement on a : Card X M . Card Y M .
Au cas où le Tableau 4.7 n’aurait pas fourni la solu tion, il aurait fallu reprendre l’algo -
rithme, après avoir affecté le plus pos sible de zéros, (ce que l’on véri fie en résol vant un
pro blème de flot maximal comme ci dessus), à la pro cé dure de mar quage, et ainsi de
suite jus qu’à l’obten tion de la solu tion (qui nécessite en général plusieurs itérations).
Une solu tion opti male consiste à affec ter : A à a ; B à e ; C à c ; D à b et Ε à d. Elle
a pour coût 10.
Telle est la méthode hon groise, à laquelle on a donné ce nom en sou ve nir de deux
mathéma ti ciens hon grois, Egervary et König, qui ont contri bué, avec Kuhn, à en
fon der la théo rie.
Tableau 4.6
A
B
C
D
E
a b c d e
0 1 2 1 2
0 3 1 2 0
2 1 0 2 1
0 1 2 2 1
1 0 3 0 2
Tableau 4.7
A
B
C
D
E
a b c d e
0 0 1 0 1
1 3 1 2 0
3 1 0 2 1
0 0 1 1 0
2 0 3 0 2