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

Un article de Wikipédia, l'encyclopédie libre.

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ée pas une relation de dualité faible :

Pour tout graphe G, la cardinalité maximum d'un couplage de G est inférieure ou égale à la cardinalité minimum 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 un triangle (graphe complet à 3 sommets).

Le théorème de König établit une relation de dualité forte pour les graphes bipartis:

Théorème de König (1931) - Pour tout graphe biparti G, la cardinalité maximum d'un couplage de G est égale à la cardinalité minimum d'un transversal de G.

Le théorème n'est pas difficile à montrer il en existe plusieurs preuves courtes (voir les références).

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 (voir graphe biparti). Et finalement, il se généralise à l'aide des matrices totalement unimodulaires.

[modifier] Références

Graph Theory with Applications, J.A. Bondy and U.S.R. Murty, libre d'accès uniquement pour l'usage personnel http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html

Graph Theory de Diestel, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.counted.pdf)