Lema de Berge

De Viquipèdia
Jump to navigation Jump to search

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]

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