Probleme – Le théorème de König

1. Soit $M$ un couplage et $C$ une couverture. Chaque arête de $M$ doit être touchée par au moins un sommet de $C$. Deux arêtes distinctes de $M$ n'ayant aucune extrémité commune, elles sont touchées par des sommets distincts. L'application « arête de $M$ $\mapsto$ un sommet de $C$ qui la touche » est donc injective, d'où $|M|\le |C|$. En passant au maximum à gauche et au minimum à droite : $\nu (G)\le \tau (G)$.

2. Sur le triangle $K_3$, $\nu =1$ — deux arêtes quelconques partagent un sommet — et $\tau =2$ — un seul sommet laisse une arête découverte. L'inégalité est stricte. C'est le cycle impair qui la rend stricte, et un graphe biparti n'en a pas.

3. La construction. Soit $G$ biparti de parties $U$ et $V$, et $M$ un couplage maximum. Notons $L\subseteq U$ l'ensemble des sommets de $U$ non saturés par $M$, et $Z$ l'ensemble des sommets atteignables depuis $L$ par des chemins alternants (arête hors $M$, puis arête de $M$, etc.). Posons

$$C=(U\setminus Z)\cup (V\cap Z).$$

$C$ est une couverture. Soit une arête $\{u,v\}$ avec $u\in U$, $v\in V$. Si $u\notin Z$, alors $u\in C$ et c'est fini. Si $u\in Z$, montrons que $v\in Z$. Si $\{u,v\}\notin M$, alors le chemin alternant qui atteint $u$ se prolonge par $\{u,v\}$ — il arrive en $u$ soit depuis $L$ directement ($u$ non saturé), soit par une arête de $M$ —, donc $v\in Z$. Si $\{u,v\}\in M$, alors $u$ est saturé, donc $u\notin L$, donc $u$ a été atteint par une arête de $M$, qui est justement $\{v,u\}$ : $v\in Z$. Dans les deux cas $v\in V\cap Z\subseteq C$.

$|C|\le |M|$. Deux observations. Premièrement, tout sommet de $U\setminus Z$ est saturé, puisque $L\subseteq Z$. Deuxièmement, tout sommet de $V\cap Z$ est saturé : sinon le chemin alternant qui l'atteint serait un chemin augmentant, ce que le théorème de Berge interdit pour un couplage maximum. Chaque sommet de $C$ est donc l'extrémité d'une arête de $M$. Enfin, aucune arête de $M$ n'a ses deux extrémités dans $C$ : si $\{u,v\}\in M$ avec $v\in V\cap Z$, on a vu que $u$ est alors atteint depuis $v$ par cette même arête de $M$, donc $u\in Z$, donc $u\notin U\setminus Z$. L'application « sommet de $C$ $\mapsto$ son arête de $M$ » est donc injective : $|C|\le |M|$.

En combinant avec la question 1 : $\nu (G)\le \tau (G)\le |C|\le |M|=\nu (G)$. Tout est égal.

Vérification : sur $4000$ graphes bipartis aléatoires, le cardinal du couplage maximum et celui de la plus petite couverture (calculée par énumération de tous les sous-ensembles de sommets) coïncident sans un seul écart.

4. La conséquence algorithmique. Le couplage maximum est calculable en $O(nm)$ ; König donne donc, dans un graphe biparti, la couverture minimale en temps polynomial — et la construction ci-dessus l'exhibe, elle ne fait pas qu'annoncer son cardinal.

C'est remarquable, car la couverture minimale dans un graphe quelconque est np-difficile : c'est le problème que le chapitre chap:gloutons n'approchait qu'à un facteur $2$. La bipartition fait passer un problème d'approximation à un problème exact, et le pont entre les deux est le couplage.

Et l'on retrouve la $2$-approximation sous un autre jour : l'algorithme glouton du chapitre chap:gloutons prend les deux extrémités de chaque arête d'un couplage maximal ; dans un graphe biparti, König dit qu'une seule extrémité bien choisie par arête d'un couplage maximum suffit. Le facteur $2$ est exactement le prix de ne pas savoir laquelle.