Lema_de_Berge Knowpia

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, 1957

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

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

Datos: Q552367

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

[1]

Summary

Referencias