Lema de Berge

De Viquipèdia
Salta a: navegació, cerca

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 matching M en un graf G es màxim si i només si no hi ha rutes augmentatives amb M.


Un matching é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 el matching.

Referències[modifica | modifica el codi]

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