Lema de berge

El lema de Berge establece que una coincidencia M en un grafo G es la más grande (contiene el mayor número posible de aristas) si y solo si no hay un camino complementario (un camino que comienza y termina en libre, es decir, que no pertenece a coincidencias, vértices y pasa alternativamente por aristas coincidentes y no coincidentes) en M.

El lema fue probado por el matemático francés Claude Berge en 1957 (aunque ya había sido discutido por Petersen en 1891 y König en 1931).

Prueba

Para probar el lema de Berge, primero necesitamos otro lema . Tome un gráfico G y sean M y M ′ dos emparejamientos en G. Sea G′ el resultado de tomar la diferencia simétrica de M y M′ . eso es G′ estará formado por componentes que pertenecen a los siguientes grupos:

  1. Parte superior aislada .
  2. Un ciclo par cuyas aristas pertenecen alternativamente a M y M′ .
  3. Un camino con extremos distintos cuyos bordes pertenecen alternativamente a M y M′ .

El lema se puede probar observando que cualquier vértice en G puede ser incidente a lo sumo en dos aristas, una desde M y otra desde M . Los gráficos en los que cualquier vértice tiene un grado máximo de 2 deben constar de vértices , ciclos y caminos aislados . Además, todo camino y ciclo en G debe estar contenido en M y M a su vez . Para que un ciclo se comporte de esta manera, debe tener el mismo número de aristas desde M y M y , por lo tanto, una longitud uniforme.

Ahora podemos probar el Lema de Berge por contradicción : un grafo G tiene una coincidencia mayor que M si y solo si G tiene un camino complementario. Está claro que el camino complementario P del gráfico G se puede usar para obtener un M′ coincidente que es mayor que el M coincidente ; simplemente tome como M′ la diferencia simétrica de los caminos P y M ( M′ consiste exactamente en esos aristas del grafo G que aparecen exactamente una vez en el camino P , o en el coincidente M ). De aquí se sigue la demostración en sentido contrario.

Para la prueba directa, sea M′ una coincidencia del gráfico G que es mayor que la coincidencia M. Considere como D la diferencia simétrica de M y M′ . Tenga en cuenta que D consta de caminos e incluso ciclos (como se señaló en el lema anterior ). Como M′ es mayor que M , D contiene un componente que tiene más aristas desde M′ que desde M. Tal componente es un camino en G que comienza y termina con una arista en M , por lo que es complementario.

Consecuencias

Corolario 1

Sea M la coincidencia más grande y considere una cadena alterna tal que los bordes en el camino alternan entre pertenecer y no pertenecer a M . Si el camino alterno es un ciclo o un camino de longitud uniforme, entonces el nuevo M′ coincidente más grande se puede encontrar intercambiando aristas entre M y no desde M. Por ejemplo, si la cadena alterna es , donde , y . El intercambio de estos bordes hará que todos los n i formen parte de la nueva combinación, y todos los m i no se incluirán en la combinación.

Consecuencia 2

Un borde se considera "libre" si pertenece a la coincidencia más grande, pero no a todas las coincidencias más grandes. Una arista e es libre si y solo si, en una coincidencia máxima arbitraria M , la arista e pertenece a un camino alterno par que comienza en un vértice descubierto o pertenece a un ciclo alterno . Por el primer corolario, si la arista e es parte de tal cadena alterna, entonces debe haber una nueva coincidencia M más grande, y e pertenecerá a M o M y, por lo tanto, es libre. Por el contrario, si la arista e está libre, entonces e está en algún M coincidente mayor , pero no en M′ . Dado que la arista e no pertenece tanto a M como a M′ , debe estar presente en la diferencia simétrica de M y M′ . La diferencia simétrica entre M y M′ da un gráfico que consta de vértices aislados, incluso ciclos alternos y caminos incluso alternos de longitud. Suponga que este no es el caso y que e pertenece a algún camino de longitud impar. Pero entonces uno de los emparejamientos M o M′ debe tener menos aristas en esta componente, lo que significa que este componente en su conjunto es un camino complementario para este emparejamiento. Según el lema original, esta coincidencia ( M o M ) no puede ser la más grande, lo que contradice la suposición de que tanto M como M son las coincidencias más grandes. Por lo tanto, como e no puede pertenecer a ningún componente de ruta de longitud impar, debe estar en un ciclo de longitud par o en una ruta de longitud par alterna.

Notas

Literatura