Théorème de Kőnig (théorie des graphes)

vignette|Exemple d'un graphe biparti avec un couplage maximum (en bleu) et une couverture de sommets minimale (en rouge), tous les deux de taille 6. Le théorème de Kőnig est un résultat de théorie des graphes qui dit que, dans un graphe biparti, la taille du transversal minimum (i. e. de la couverture par sommets minimum) est égale à la taille du couplage maximum. La version pondérée du théorème est appelée théorème de Kőnig-. Un couplage d'un graphe G est un sous-ensemble d'arêtes de G deux-à-deux non adjacentes ; un sommet est couplé s'il est extrémité d'une arête du couplage. Un transversal de G est un sous-ensemble T de sommets de G avec la propriété que toute arête de G est incidente à au moins un sommet de T (on dit aussi que T couvre les arêtes de G et l'on appelle aussi T une couverture nodale de G). Ces deux invariants sont reliés par une relation de dualité faible : La preuve réside dans le fait qu'un sommet ne peut couvrir plus d'une arête d'un couplage. L'inégalité est vraie en particulier du cardinal maximum d'un couplage et du cardinal minimum d'un transversal. Remarquons que cette inégalité peut être stricte, comme c'est le cas si G est le graphe triangle (le graphe complet à 3 sommets). Le théorème de Kőnig établit une relation de dualité forte pour les graphes bipartis : Ce théorème n'est pas difficile à démontrer ; il en existe plusieurs preuves courtes (voir la référence). On donne ici une démonstration constructive, qui donne un algorithme pour trouver un transversal minimal à partir d'un couplage maximal M pour le graphe G. Comme G est biparti, ses sommets se répartissent en deux ensembles U et V et pour les arêtes (u,v) il sera entendu que u ∈ U et que v ∈ V. Soit Z l'ensemble des sommets de U qui ne sont pas couplés par M. Puis ajoutons à Z tous les sommets atteignables à partir de Z par des chemins alternants, c'est-à-dire dont les arêtes sont alternativement non dans M puis dans M. La construction de Z implique que pour chaque arête (u,v) de M, si v ∈ Z alors u ∈ Z également.