Theoreme de Konig (theorie des graphes)

Theoreme de Konig (theorie des graphes)

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

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.


Références

  • Reinhard Diestel : Graph Theory. Springer-Verlag Heidelberg, New York, 1997, 2000, 2005. Version électronique de la 3e édition disponible en ligne gratuitement : [1]
Ce document provient de « Th%C3%A9or%C3%A8me de K%C3%B6nig (th%C3%A9orie des graphes) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Theoreme de Konig (theorie des graphes) de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Théorème de könig (théorie des graphes) — 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… …   Wikipédia en Français

  • Théorème de König (théorie des graphes) — Pour les articles homonymes, voir Théorème de König. 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 …   Wikipédia en Français

  • Theoreme de Konig — Théorème de König Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Il existe plusieurs « théorèmes de König » pour la simple raison qu il existe plusieurs scientifiques portant le nom de König… …   Wikipédia en Français

  • Théorème de könig — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Il existe plusieurs « théorèmes de König » pour la simple raison qu il existe plusieurs scientifiques portant le nom de König (que l on… …   Wikipédia en Français

  • Théorème de König — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Il existe plusieurs « Théorèmes de König » pour la simple raison qu il existe plusieurs scientifiques portant le nom de König (écrit aussi… …   Wikipédia en Français

  • Theoreme flot-max/coupe-min — Théorème flot max/coupe min Le théorème flot max/coupe min est un théorème de la théorie des graphes. Il généralise le théorème de König et le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques).… …   Wikipédia en Français

  • Théorème flot-max/coupe-min — Le théorème flot max/coupe min est un théorème de la théorie des graphes. Il généralise le théorème de König et le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques). Il révèle que le calcul d une …   Wikipédia en Français

  • Théoreme de Hall — Théorème de Hall Le théorème de Hall donne une condition nécessaire et suffisante à l existence d un couplage parfait dans un graphe biparti (un couplage parfait dans un graphe ayant un nombre pair 2n de sommets est un sous ensemble de n arêtes… …   Wikipédia en Français

  • Théorème de hall — Le théorème de Hall donne une condition nécessaire et suffisante à l existence d un couplage parfait dans un graphe biparti (un couplage parfait dans un graphe ayant un nombre pair 2n de sommets est un sous ensemble de n arêtes deux à deux… …   Wikipédia en Français

  • Théorème de Hall —  Ne pas confondre avec le théorème de Hall en théorie des groupes, ni avec le problème des ménages. En mathématiques, le théorème de Hall ou lemme des mariages est un résultat combinatoire qui donne une condition nécessaire et suffisante,… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”