Théorème de Kőnig (théorie des graphes)
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-Egerváry (en).
Définitions
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 :
Dans tout graphe, le cardinal de tout couplage est inférieur ou égal au cardinal de tout transversal.
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).
Théorème
Le théorème de Kőnig établit une relation de dualité forte pour les graphes bipartis :
Théorème (Dénes Kőnig, 1931) — Pour tout graphe biparti G, le cardinal maximal d'un couplage de G est égal au cardinal minimal d'un transversal de G.
Preuve
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. Et si u ∈ Z, comme u n'était pas initialement dans les sommets libres de U, u a été ajouté à Z grâce à l'arête (u,v), donc v ∈ Z. Ceci implique que pour chaque arête du couplage M, soit ses deux extrémités sont dans Z soit aucune.
Autrement dit, en notant S := (U − Z) ∪ (V ∩ Z), toute arête du couplage a exactement une extrémité dans S, donc |S| ≥ |M|.
On va montrer que S couvre toutes les arêtes du graphe. Soit (u,v) une arête du graphe. Si u ∉ Z, alors u ∈ S et l'arête est couverte, alors supposons u ∈ Z. Si (u,v) est dans M, alors par l'observation précédente v ∈ Z, et donc v ∈ S. Si (u,v) n'est pas dans M, alors par maximalité de Z, v doit aussi être dans Z, donc dans S. Ceci montre que S est un transversal.
Au vu de la relation de dualité faible ci-dessus |S| ≤ |M|, nous pouvons conclure |S| = |M|.
Intérêt et généralisations
L'intérêt du théorème de Kőnig est multiple. Premièrement, il est à l'origine, avec le théorème de Menger et le théorème flot-max/coupe-min, des théorèmes min-max en optimisation combinatoire. Deuxièmement, il fournit une caractérisation polyédrale des graphes bipartis. Et finalement, il se généralise à l'aide des matrices totalement unimodulaires.
Référence
- (en) Reinhard Diestel, Graph Theory [détail des éditions]