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. Il est aussi appelé théorème de König-Egerváry (en).

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).

La preuve du théorème est constructive, et donne un algorithme pour trouver une couverture minimale à partir d'un couplage maximal M pour le graphe G(U,V,E). Soit Z l'ensemble des sommets pas couplés par M, et qui sont dans U. Puis ajoutons dans Z tous les sommets atteignables à partir de Z par des chemins alternants. On définit un ensemble S := (U - Z) union (V intersection Z).

La construction de Z implique que pour chaque arête (u,v) in M si v in Z alors u in Z également. Et si u in Z, comme u n'était pas initialement dans Z avec les sommets libres de U, u a été ajouté à Z grâce à l'arête du couplage, donc v in Z.

Ceci implique que pour chaque arête du couplage (u,v) in M, soit tous les deux extrémités sont dans Z soit aucune. Donc toute arête du couplage a exactement une extrémité dans S, et donc |S|≥|M|. Combiné avec l'observation précédente |S|≤|M|, nous pouvons conclure |S|=|M|.

On va montrer que S couvre toutes les arêtes du graphe. Soit (u,v) une arête du graphe. Si u in Z, l'arête est couverte, alors supposons que u not in Z. Si (u,v) n'est pas une arête du couplage, alors par maximalité de Z, v doit aussi être dans Z, et est donc dans S. Si (u,v) est dans M, alors par l'observation précédente v in Z, et donc v in S. Ceci montre que S est une couverture de sommets.

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]