Lema de Berge

Lema de Berge

En teoría de grafos, el Lema de Berge es un lema demostrado por el matemático francés Claude Berge en 1957,[1] que dice lo siguiente:

Un matching M en un grafo G es máximo si y sólo si no hay rutas aumentativas con M.

Un matching es máximo si contiene el mayor número de aristas posibles.

Una ruta aumentativa (augmenting path) es un camino que comienza y termina en vértices libres o no conectados, y alterna entre aristas que están y no están en el matching.

Referencias

  1. ↑ C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957)

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Claude Berge — Nacimiento 5 de junio de 1926  Francia Fallecimiento 30 de junio de 2002 …   Wikipedia Español

  • Monte Lema — aus dem Val Veddasca Höhe 1 624 m ü. M …   Deutsch Wikipedia

  • Soiusa — La Subdivision Orographique Internationale Unifiée du Système Alpin ou SOIUSA ((it) Suddivisione Orografica Internazionale Unificata del Sistema Alpino) est une des classifications systématiques des massifs alpins. Sommaire 1 Histoire 2 Concept… …   Wikipédia en Français

  • Demokratische Republik Kongo — République Démocratique du Congo (Französisch) Republiki ya Kongó Demokratiki (Kikongo) Ditunga dia Kongu wa Mungalaata (Tschiluba) Repubilika ya Kongo ya Dimokalasi (Lingala) Jamhuri ya Kidemokrasia ya Kongo (Swahili) Demokratische Republik… …   Deutsch Wikipedia

  • Killi — Pour les articles homonymes, voir Porophyllum ruderale. Nom vernaculaire ou nom normalisé ambigu : Le terme « Killi » s applique en français à plusieurs taxons distincts …   Wikipédia en Français

  • Liste des groupes ayant été programmés lors des Rencontres Trans Musicales — Article principal : Rencontres Trans Musicales. Groupes ayant été programmés lors des Rencontres Trans Musicales de Rennes depuis leur création. Sommaire 1 Édition 2010 2 Édition 2009 3 Édition 2008 …   Wikipédia en Français

  • Austria — Republik Österreich República de Austria …   Wikipedia Español

  • Euskadi Ta Askatasuna — Saltar a navegación, búsqueda Euskadi Ta Askatasuna (ETA) Pintada con el anagrama de ETA Operacional 1959 presente Objetivos La creación de un estado independi …   Wikipedia Español

  • Breslavia — Wrocław Breslavia Bandera …   Wikipedia Español

  • Grupos de Combate de la Clase Obrera — Kampfgruppen der Arbeiterklasse Grupos de Combate de la Clase Obrera Bandera de los GCCO. Activa 1953 1990 …   Wikipedia Español

Compartir el artículo y extractos

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