Lema de Berge
En teoria de grafs, el lema de Berge és un lema demostrat pel matemàtic francès Claude Berge el 1957,[1] que diu el següent:
|
Un aparellament és màxim si conté el major nombre d'arestes possibles. Una ruta augmentativa (en anglès augmenting path) és un camí que comença i acaba en vèrtexs lliures o no connectats, i alterna entre arestes que estan i no estan en l'aparellament.
Referències
[modifica]- ↑ C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957)