König Dénes

Imaginez deux rangées de points : des personnes d'un côté et des tâches de l'autre. Une ligne relie une personne à une tâche qu'elle peut accomplir. Un couplage choisit des lignes sans partager de point, tandis qu'une couverture choisit des points qui touchent toutes les lignes. Dans un graphe biparti, le plus grand nombre de lignes disjointes et le plus petit nombre de points couvrant toutes les lignes sont toujours égaux. Le théorème de König transforme ainsi deux façons différentes de compter une même organisation.

Le théorème de König concerne un graphe biparti, c'est-à-dire un graphe dont les sommets sont répartis en deux ensembles et dont chaque arête relie un ensemble à l'autre. Un couplage est un ensemble d'arêtes qui n'ont aucun sommet en commun. Sa cardinalité est le nombre d'arêtes retenues. Une couverture de sommets est un ensemble de sommets tel que chaque arête possède au moins une extrémité dans cet ensemble.

Si μ désigne la cardinalité maximale d'un couplage et τ la cardinalité minimale d'une couverture de sommets, le théorème affirme :
Cette égalité vaut pour tout graphe biparti fini. Elle compare donc une sélection d'arêtes, où aucun sommet ne peut être réutilisé, avec une sélection de sommets, où chaque arête doit être touchée. Le nom de König-Egerváry est également employé pour ce résultat.

Considérons un graphe biparti dont la première partie contient les sommets A₁, A₂ et A₃, et la seconde les sommets B₁, B₂ et B₃. Ses arêtes sont A₁–B₁, A₁–B₂, A₂–B₂, A₂–B₃ et A₃–B₃.

Un couplage de trois arêtes est A₁–B₁, A₂–B₂ et A₃–B₃. Ces arêtes n'ont aucun sommet commun, donc sa cardinalité vaut 3.

Une couverture de sommets est formée par A₁, A₂ et A₃. Chaque arête possède une extrémité parmi ces trois sommets, donc sa cardinalité vaut 3.
Le couplage ne peut pas compter plus de trois arêtes, car il ne peut utiliser que les trois sommets de la première partie sans les réutiliser. La couverture proposée atteint aussi trois sommets. Les deux valeurs sont donc égales : μ = τ = 3.

Le contrôle est direct : chaque arête de la liste touche A₁, A₂ ou A₃, et les trois arêtes du couplage ont six extrémités distinctes. Le résultat vérifie bien l'égalité annoncée.

En affectation, les sommets d'un côté représentent des personnes et ceux de l'autre des tâches. Une arête signifie qu'une affectation est possible. Chercher un couplage maximum revient à retenir le plus grand nombre d'affectations compatibles, sans attribuer deux tâches à la même personne ni une même tâche à deux personnes.

Pour vérifier qu'une affectation est optimale, on peut chercher une couverture de sommets de même cardinalité. Si elle touche toutes les arêtes, elle fournit une borne supérieure ; un couplage de même taille fournit la borne inférieure correspondante.

En optimisation combinatoire et en recherche opérationnelle, cette égalité permet de relier une solution construite par des arêtes à un certificat construit par des sommets. Lorsque les compatibilités ne forment pas un graphe biparti, une méthode propre au cas biparti ne se transpose pas automatiquement.

Le théorème de König-Egerváry ne doit pas être confondu avec une formule portant le nom de König-Huygens. Le premier relie, dans un graphe biparti, un couplage maximum et une couverture de sommets minimum ; la seconde concerne la variance en probabilités. Le critère qui tranche est l'objet étudié : arêtes et sommets d'un graphe d'un côté, valeurs numériques et dispersion de l'autre.

La bipartition est une condition décisive. Si une arête relie deux sommets placés dans le même ensemble, cette répartition n'est pas une bipartition valide ; cela ne suffit pas à conclure que le graphe n'est pas biparti, car une autre répartition peut convenir. Il faut donc vérifier la répartition des sommets et, si nécessaire, rechercher une autre bipartition avant d'invoquer l'égalité entre couplage maximum et couverture minimum.

Un couplage maximum et une couverture minimum ne sont pas nécessairement uniques. Dans l'exemple, la couverture {A₁, A₂, A₃} a trois sommets, mais d'autres couvertures de trois sommets peuvent exister. Le théorème garantit l'égalité des cardinalités, pas l'unicité des ensembles choisis.

Le mot « maximum » qualifie le nombre d'arêtes du couplage, tandis que « minimal » ou « minimum » qualifie le nombre de sommets de la couverture. Une couverture simplement minimale, dont aucun sommet ne peut être retiré, n'a pas forcément une cardinalité minimum. Il faut comparer les nombres, et non seulement constater l'absence de retrait possible.

Le théorème de König-Egervary présente le résultat sous son autre appellation et permet d'approfondir la relation entre couplages et couvertures dans les graphes bipartis.