- 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.
Claude Berge, 1957Un 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
- ↑ C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957)
Categorías:- Teoremas de teoría de grafos
- Lemas (matemáticas)
Wikimedia foundation. 2010.