Comprendre la preuve liée à l'algorithme hongrois
Je regarde l'interprétation de la matrice de l'algorithme hongrois (et plus précisément l'astuce nécessaire pour les étapes 3 et 4 sur la page Wikipédia sur le https://en.wikipedia.org/wiki/Hungarian_algorithm) et en essayant de comprendre la preuve suivante liée à cela.
J'ai juste une question à propos de cette preuve puisqu'elle n'est pas expliquée dans le texte: pourquoi est-ce exactement que la matrice $\boldsymbol{E}$ a $b$ des zéros indépendants (et $\boldsymbol{D}$ a $a$)? Je ne peux pas comprendre cela, donc si quelqu'un peut expliquer, je serais reconnaissant.
Réponses
Il y a $a$ lignes, et ceci est indiqué par les matrices $C$ et $D$.
Il y a $b$ colonnes, et ceci est indiqué par les matrices $C$ et $E$.
Ils ne sont pas multipliés, car la notation matricielle utilisée est augmentée .
Donc, $D$ a $a$ des zéros et $E$ a $b$ des zéros.
Une preuve beaucoup plus simple de ce que l'auteur essaie de prouver est qu'il peut y avoir au plus $l=\min(m,n)$ zéros par le principe du casier (s'il y a plus de $l$, au moins une ligne / colonne contient deux zéros), puis fournissez un exemple de matrice avec $l$ des zéros, par exemple une ligne diagonale de zéros à partir d'un coin.