Hispanopedia Wiki
Articulo de referencia

Teorema de Berge

Se muestra que una coincidencia , denotada en azul, no es una coincidencia de cardinalidad máxima debido a la presencia de una ruta de aumento , con puntos finales en los vértic...

Hispanopedia WikiContenido en espanolLectura gratuita
Se muestra que una coincidencia , denotada en azul, no es una coincidencia de cardinalidad máxima debido a la presencia de una ruta de aumento , con puntos finales en los vértices amarillos.

En teoría de grafos , el teorema de Berge establece que un emparejamiento M en un grafo G es máximo (contiene el mayor número posible de aristas) si y solo si no existe un camino de aumento (un camino que comienza y termina en vértices libres (no emparejados) y alterna entre aristas que están y no están en el emparejamiento) con M.

Fue demostrado por el matemático francés Claude Berge en 1957 (aunque ya había sido observado por Petersen en 1891 y Kőnig en 1931).

Prueba

Para demostrar el teorema de Berge, primero necesitamos un lema . Tomemos un grafo G y sean M y M ′ dos emparejamientos en G. Sea G ′ el grafo resultante de tomar la diferencia simétrica de M y M ′ ; es decir, ( M - M ′ ) ∪ ( M ′ - M ). G ′ estará formado por componentes conexas que son una de las siguientes:

  1. Un vértice aislado .
  2. Un ciclo par cuyos bordes alternan entre M y M ′ .
  3. Un camino cuyos bordes alternan entre M y M ′ , con puntos finales distintos.

El lema se puede demostrar observando que cada vértice en G ′ puede ser incidente a lo sumo 2 aristas: una de M y otra de M ′ . Los grafos donde cada vértice tiene grado menor o igual a 2 deben consistir en vértices aislados , ciclos y caminos . Además, cada camino y ciclo en G ′ debe alternar entre M y M ′ . Para que un ciclo cumpla esta condición, debe tener un número igual de aristas de M y M ′ , y por lo tanto, tener una longitud par.

Demostremos ahora la contrapositiva del teorema de Berge: G tiene un emparejamiento mayor que M si y solo si G tiene un camino de aumento. Claramente, un camino de aumento P de G puede usarse para producir un emparejamiento M ′ mayor que M ; basta con considerar M ′ como la diferencia simétrica de P y M ( M ′ contiene exactamente aquellas aristas de G que aparecen en solo uno de P y M ). Por lo tanto, se deduce la relación inversa.

Para la dirección hacia adelante, sea M ′ un emparejamiento en G mayor que M. Consideremos D , la diferencia simétrica de M y M ′ . Observemos que D consta de caminos e incluso ciclos (como se observa en el lema anterior). Dado que M ′ es mayor que M , D contiene un componente que tiene más aristas de M ′ que de M. Dicho componente es un camino en G que comienza y termina con una arista de M ′ , por lo que es un camino de aumento.

Corolarios

Corolario 1

Sea M un emparejamiento máximo y consideremos una cadena alternada tal que las aristas en el camino alternan entre estar y no estar en M. Si la cadena alternada es un ciclo o un camino de longitud par que comienza en un vértice no emparejado, entonces se puede encontrar un nuevo emparejamiento máximo M ′ intercambiando las aristas que se encuentran en M y las que no están en M. Por ejemplo, si la cadena alternada es (m1, n1 , m2 , n2 , ... ) , donde mᵢ ∈ M y nᵢ ∉ M , intercambiarlas haría que todos los nᵢ formaran parte del nuevo emparejamiento y que todos los mᵢ no formaran parte del emparejamiento.

Corolario 2

Una arista se considera "libre" si pertenece a un emparejamiento máximo pero no pertenece a todos los emparejamientos máximos. Una arista e es libre si y solo si, en un emparejamiento máximo arbitrario M , la arista e pertenece a un camino alternante par que comienza en un vértice no emparejado o a un ciclo alternante . Por el primer corolario, si la arista e es parte de tal cadena alternante, entonces debe existir un nuevo emparejamiento máximo, M ′ , y e existiría en M o M ′ , y por lo tanto sería libre. Recíprocamente, si la arista e es libre, entonces e está en algún emparejamiento máximo M pero no en M ′ . Como e no es parte de M y M ′ , debe seguir existiendo después de tomar la diferencia simétrica de M y M ′ . La diferencia simétrica de M y M ′ da como resultado un grafo que consta de vértices aislados, ciclos alternantes pares y caminos alternantes. Supongamos por el contrario que e pertenece a algún componente de camino de longitud impar. Pero entonces uno de M o M ′ debe tener una arista menos que el otro en este componente, lo que significa que el componente en su conjunto es un camino de aumento con respecto a ese emparejamiento. Por el lema original, entonces, ese emparejamiento (ya sea M o M ′ ) no puede ser un emparejamiento máximo, lo que contradice la suposición de que tanto M como M ′ son máximos. Así pues, dado que e no puede pertenecer a ningún componente de camino de longitud impar, debe estar en un ciclo alternante o en un camino alternante de longitud par.

Referencias