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

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Théorème de König.

Le théorème de König est un résultat de théorie des graphes qui exprime l'égalité de deux paramètres, la taille du transversal minimum (i. e. de la couverture par sommets minimum) et la taille du couplage maximum, dans le cas des graphes bipartis.

Définitions[modifier | modifier le code]

En théorie des graphes, un couplage d'un graphe G est un sous-ensemble d'arêtes de G deux-à-deux non adjacentes. Un transversal de G est un sous-ensemble de sommets T 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 :

Pour tout graphe G, la cardinalité maximale d'un couplage de G est inférieure ou égale à la cardinalité minimale d'un transversal de G.

La preuve réside dans le fait qu'un sommet ne peut couvrir plus d'une arête d'un couplage). Remarquons que l'inégalité peut être stricte comme c'est le cas si G est le graphe triangle (le graphe complet à 3 sommets).

Théorème[modifier | modifier le code]

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, la cardinalité maximale d'un couplage de G est égale à la cardinalité minimale d'un transversal de G.

Preuve[modifier | modifier le code]

Ce théorème n'est pas difficile à démontrer, il en existe plusieurs preuves courtes (voir la référence).

Intérêt et généralisations[modifier | modifier le code]

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[modifier | modifier le code]

(en) Reinhard Diestel (de), Graph Theory, Springer-Verlag, Heidelberg, New York, 1997, 2000, 2005. Version électronique de la 3e édition disponible en ligne gratuitement

Voir aussi[modifier | modifier le code]