théorème de König-Egervary

Imaginez des personnes d’un côté et des tâches de l’autre. Une arête relie une personne à chaque tâche qu’elle peut assurer. Un couplage choisit des affectations sans employer deux fois la même personne ni la même tâche.

Le théorème affirme une égalité surprenante. Le plus grand nombre d’affectations compatibles est aussi le plus petit nombre de personnes ou de tâches qu’il faut sélectionner pour toucher toutes les possibilités. Une solution maximale et un obstacle minimal portent donc le même nombre.

Un graphe biparti G répartit ses sommets en deux ensembles, notés X et Y, et chaque arête relie un sommet de X à un sommet de Y. Un couplage est un ensemble d’arêtes dont aucune paire ne partage de sommet. Sa taille maximale est notée ν(G).

Une couverture de sommets, aussi appelée transversal dans la définition de référence, est un ensemble de sommets qui contient au moins une extrémité de chaque arête. Sa taille minimale est notée τ(G). Le théorème de König-Egerváry énonce l’identité $\nu (G)=\tau (G)\backslash nu(G)=\backslash tau(G)$ pour tout graphe biparti fini. L’égalité compare des nombres : elle ne dit ni que le couplage et la couverture sont uniques, ni qu’ils contiennent les mêmes objets.

Le résultat est une dualité min-max. Tout couplage fournit une borne inférieure pour toute couverture, car chacune de ses arêtes disjointes exige un sommet distinct pour être couverte. La propriété particulière des graphes bipartis garantit qu’une couverture atteignant cette borne existe.

Si G est un graphe biparti fini, si ν(G) désigne le nombre maximal d’arêtes deux à deux sans sommet commun et si τ(G) désigne le nombre minimal de sommets couvrant toutes les arêtes, alors :

Un couplage de taille k et une couverture de k sommets suffisent donc à certifier simultanément que les deux solutions sont optimales.

Le graphe doit être biparti : ses sommets doivent pouvoir être séparés en deux ensembles X et Y sans arête à l’intérieur d’un même ensemble. Il faut aussi comparer deux objets précis, un couplage d’arêtes sans sommet commun et une couverture composée de sommets touchant chaque arête. Pour le cadre élémentaire de cette fiche, le graphe est fini.

Le triangle fournit un contre-cas immédiat. Il n’est pas biparti, son plus grand couplage contient une seule arête, tandis qu’il faut deux sommets pour couvrir ses trois arêtes. L’égalité échoue donc : ν(G) = 1 mais τ(G) = 2. Pour un graphe non biparti, il faut employer des résultats de couplage plus généraux plutôt que cette identité.

Prenons X = {A, B, C} et Y = {1, 2, 3}. Les cinq arêtes sont A–1, A–2, B–2, C–2 et C–3. Le schéma met en évidence un couplage et une couverture de même taille.

1. Choisissons A–1, B–2 et C–3. Ces trois arêtes n’ont aucun sommet commun : elles forment un couplage de taille 3.
2. Un couplage ne peut pas dépasser 3, car X ne contient que trois sommets. Ainsi, ν(G) = 3.
3. Sélectionnons les sommets A, 2 et C. A couvre A–1 et A–2 ; 2 couvre B–2 et C–2 ; C couvre aussi C–3. Toutes les arêtes sont couvertes.
4. Une couverture doit toucher séparément les trois arêtes disjointes A–1, B–2 et C–3. Elle contient donc au moins trois sommets. Ainsi, τ(G) = 3.

Le contrôle est complet : une solution de chaque type atteint la borne imposée par l’autre. On vérifie donc ν(G) = τ(G) = 3, comme l’annonce le théorème.

Dans un problème d’affectation où chaque compatibilité vaut simplement oui ou non, un couplage maximum donne le plus grand nombre d’affectations simultanées. Une recherche exhaustive devient inutile dès qu’une méthode de couplage adaptée est disponible.

La couverture minimum explique aussi ce qui limite l’affectation. Si un couplage et une couverture ont la même taille, leur égalité fournit un certificat d’optimalité que l’on peut vérifier arête par arête.

Lorsque les affectations portent des coûts ou des préférences, la seule cardinalité ne suffit plus. Le théorème reste un repère structurel, mais il faut alors un modèle d’optimisation qui prend ces valeurs en compte.

Un couplage maximum contient autant d’arêtes que possible dans tout le graphe. Un couplage seulement maximal ne peut plus être agrandi localement, mais peut être plus petit. Le critère qui tranche est l’existence d’un autre couplage de plus grande taille.

Une couverture de sommets choisit des sommets touchant toutes les arêtes. Elle ne doit pas être confondue avec un ensemble d’arêtes destiné à toucher tous les sommets : les objets sélectionnés et ceux qui doivent être couverts sont inversés.

Le théorème de König-Egerváry concerne les graphes bipartis. Il ne s’agit pas de la formule de König-Huygens, qui appartient à un autre contexte mathématique ; la présence d’un graphe, d’un couplage et d’une couverture lève l’ambiguïté.

Graphe non biparti. Un cycle impair signale que l’hypothèse peut échouer. Dans le triangle, ν(G) = 1 et τ(G) = 2 ; il ne faut pas appliquer l’égalité de König-Egerváry.

Solutions non uniques. L’égalité porte seulement sur les tailles optimales. Dans l’exemple, plusieurs couplages de taille 3 peuvent exister ; il faut vérifier la cardinalité et les contraintes, sans chercher une solution canonique.

Sommets isolés. Un sommet sans arête ne change ni le couplage maximum ni la couverture minimum. Il ne doit pas être ajouté à une couverture sous prétexte qu’il appartient au graphe.

Graphe sans arête. Les deux optima valent 0 : le couplage vide est maximum et la couverture vide couvre toutes les arêtes. Ce cas dégénéré respecte bien le théorème.

Le graphe biparti précise la structure en deux ensembles qui rend possible l’égalité entre couplage maximum et couverture minimum.

L’article R.O. et santé : les problèmes d'affectation montre comment des choix d’affectation apparaissent dans une situation d’optimisation concrète.