En la teoría de grafos , el lema de Berge establece que una M coincidente en una gráfica G es máxima (contiene el mayor número posible de aristas) si y solo si no hay una ruta de aumento (una ruta que comienza y termina en vértices libres (no emparejados), y alterna entre los bordes de y no en el juego) con M .
Fue probado por el matemático francés Claude Berge en 1957 (aunque ya lo observaron Petersen en 1891 y Kőnig en 1931).
Prueba
Para probar el lema de Berge, primero necesitamos otro lema . Tome una gráfica G y dejar que M y M ' sean dos emparejamientos en G . Sea G ′ la gráfica resultante de tomar la diferencia simétrica de M y M ′ ; es decir, ( M - M ′ ) ∪ ( M ′ - M ). G ′ constará de componentes conectados que sean uno de los siguientes:
- Un vértice aislado .
- Un ciclo par cuyas aristas alternan entre M y M ′ .
- Un camino cuyos bordes alternan entre M y M ′ , con puntos finales distintos.
El lema se puede probar observando que cada vértice en G ′ puede incidir como máximo en 2 aristas: una desde M y otra desde M ′ . Los gráficos en los que cada vértice tiene un grado menor o igual a 2 deben constar de vértices , ciclos y trayectos aislados . Además, cada camino y ciclo en G ′ debe alternar entre M y M ′ . Para que un ciclo haga esto, debe tener el mismo número de aristas desde M y M ′ y, por lo tanto, tener una longitud uniforme.
Probemos ahora el contrapositivo del lema de Berge: G tiene una correspondencia mayor que M si y solo si G tiene un camino de aumento. Claramente, un camino de aumento P de G se puede usar para producir un M ′ coincidente que sea más grande que M ; simplemente tome M ′ como la diferencia simétrica de P y M ( M ′ contiene exactamente los bordes de G que aparecen exactamente en uno de P y M ). Por tanto, sigue la dirección inversa.
Para la dirección de avance, deja que M ' sea una coincidencia en G más grande que M . Considere D , la diferencia simétrica de M y M ′ . Observe que D consta de trayectorias e incluso ciclos (como se observa en el lema anterior ). Desde M ' es mayor que M , D contiene un componente que tiene más bordes de M' que M . Tal componente es una ruta en G que comienza y termina con un borde de M ′ , por lo que es una ruta de aumento.
Corolarios
Corolario 1
Deje que M sea un juego máximo y debe tener en cuenta una cadena de alterna de tal manera que los bordes en los suplentes trayectoria entre ser y no ser en M . Si la cadena alterna es un ciclo o un camino de longitud par, entonces una nueva coincidencia máxima M ' se puede encontrar mediante el intercambio de los bordes que se encuentran en M y no en M . Por ejemplo, si la cadena alterna es ( m 1 , n 1 , m 2 , n 2 , ...), donde m i ∈ M y n i ∉ M , intercambiarlos haría que todos n i formen parte de la nueva coincidencia y hacer que todos m i no formen parte de la correspondencia.
Corolario 2
Una ventaja se considera "libre" si pertenece a una coincidencia máxima pero no pertenece a todas las coincidencias máximas. Una arista e es libre si y sólo si, en una coincidencia máxima arbitraria M , la arista e pertenece a una trayectoria alterna uniforme que comienza en un vértice no emparejado o en un ciclo alterno . Según el primer corolario, si el borde e es parte de dicha cadena alterna, entonces debe existir una nueva coincidencia máxima, M ′ , y e existiría en M o M ′ , y por lo tanto sería libre. Por el contrario, si el borde e está libre, entonces e está en algún M de coincidencia máxima pero no en M ′ . Dado que e no es parte de M y M ′ , aún debe existir después de tomar la diferencia simétrica de M y M ′ . La diferencia simétrica de M y M ′ da como resultado un gráfico que consta de vértices aislados, incluso ciclos alternos y caminos alternos. Supongamos por el contrario que e pertenece a algún componente de trayectoria de longitud impar. Pero entonces uno de M y M ′ debe tener un borde menos que el otro en este componente, lo que significa que el componente en su conjunto es una ruta de aumento con respecto a esa coincidencia. Por lo tanto, según el lema original, esa coincidencia (ya sea M o M ′ ) no puede ser una coincidencia máxima, lo que contradice la suposición de que tanto M como M ′ son máximos. Entonces, dado que e no puede pertenecer a ningún componente de trayectoria de longitud impar, debe estar en un ciclo alterno o en una trayectoria alterna de longitud par.
Referencias
- Berge, Claude (15 de septiembre de 1957), "Dos teoremas en la teoría de grafos" (PDF) , Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 43 (9): 842–844, doi : 10.1073 / pnas. 43.9.842 , PMC 534337 , PMID 16590096.
- West, Douglas B. (2001), Introducción a la teoría de grafos (2ª ed.), Pearson Education, Inc., págs. 109–110, ISBN 81-7808-830-4.
- Berge, Claude (1973), Graphs and Hypergraphs , North-Holland Publishing Company, págs. 122-125, ISBN 0-444-10399-6.