Lema de Berge
En teoria de grafos, el Lema de Berge és un lema demostrat pel matemàtic francés Claude Berge en 1957,[1] que diu lo següent:
|
Un matching és màxim si conté el major número d'arestes possibles.
Una ruta aumentativa (augmenting path) és un camí que comença i termina en vèrtiços lliures o no conectats, i alterna entre arestes que estan i no estan en el matching.
Referències
[editar | editar còdic]- ↑ C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957)
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Lema de Berge» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.