Théorème de menger

Théorème de menger

Théorème de Menger

En théorie des graphes, le théorème de Menger est à l'origine du théorème flot-max/coupe-min qui le généralise. Il fut prouvé par Karl Menger en 1927.

Le théorème de Menger s'énonce ainsi : le nombre minimum d'arêtes dont la suppression déconnecte deux sommets s et t est égal au nombre maximum de chemins arête-disjoints reliant s et t.

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 ou consulter le Graph Theory de Diestel, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.counted.pdf

Ce document provient de « Th%C3%A9or%C3%A8me de Menger ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème de menger de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Theoreme de Menger — Théorème de Menger En théorie des graphes, le théorème de Menger est à l origine du théorème flot max/coupe min qui le généralise. Il fut prouvé par Karl Menger en 1927. Le théorème de Menger s énonce ainsi : le nombre minimum d arêtes dont… …   Wikipédia en Français

  • Théorème de Menger — En théorie des graphes, le théorème de Menger est à l origine du théorème flot max/coupe min qui le généralise. Il fut prouvé par Karl Menger en 1927. Le théorème de Menger s énonce ainsi : le nombre minimum d arêtes dont la suppression… …   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

  • 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… …   Wikipédia en Français

  • 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

  • Théorème du minimax — de von Neumann John von Neumann …   Wikipédia en Français

  • Théorème fondamental de la théorie des jeux — Théorème du minimax de von Neumann John von Neumann …   Wikipédia en Français

  • Théorème du minimax de von Neumann — John von Neumann Vers où faut il …   Wikipédia en Français

Share the article and excerpts

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