Vés al contingut

Lema de Berge

De la Viquipèdia, l'enciclopèdia lliure

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


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]
  1. C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957)