Descomposición de Gallai-Edmonds

Partición de los vértices de un grafo que proporciona información sobre la estructura de las correspondencias máximas

Una ilustración de los tres conjuntos en la descomposición de Gallai-Edmonds de un gráfico de ejemplo.

En teoría de grafos , la descomposición de Gallai-Edmonds es una partición de los vértices de un grafo en tres subconjuntos que proporciona información sobre la estructura de las coincidencias máximas en el grafo. Tibor Gallai ^{[1] [2]} y Jack Edmonds ^[3] la descubrieron de forma independiente y demostraron sus propiedades clave.

La descomposición de Gallai-Edmonds de un gráfico se puede encontrar utilizando el algoritmo Blossom .

Propiedades

Dado un grafo , su descomposición de Gallai–Edmonds consta de tres conjuntos disjuntos de vértices, , , y , cuya unión es : el conjunto de todos los vértices de . Primero, los vértices de se dividen en vértices esenciales (vértices que están cubiertos por cada coincidencia máxima en ) y vértices no esenciales (vértices que quedan sin cubrir por al menos una coincidencia máxima en ). El conjunto se define para contener todos los vértices no esenciales. Los vértices esenciales se dividen en y : el conjunto se define para contener todos los vértices esenciales adyacentes a al menos un vértice de , y se define para contener todos los vértices esenciales no adyacentes a ningún vértice de . ^[4] ${\displaystyle G}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle D(G)}$ ${\displaystyle V(G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle A(G)}$ ${\displaystyle D(G)}$ ${\displaystyle C(G)}$ ${\displaystyle D(G)}$

Es común identificar los conjuntos , , y con los subgrafos inducidos por esos conjuntos. Por ejemplo, decimos "los componentes de " para referirnos a los componentes conexos del subgrafo inducido por . ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$

La descomposición de Gallai-Edmonds tiene las siguientes propiedades: ^[5]

1. Los componentes de son grafos de factor crítico : cada componente tiene un número impar de vértices y, cuando se omite alguno de estos vértices, existe una correspondencia perfecta de los vértices restantes. En particular, cada componente tiene una correspondencia casi perfecta: una correspondencia que cubre todos los vértices menos uno. ${\displaystyle D(G)}$
2. El subgrafo inducido por tiene una coincidencia perfecta. ${\displaystyle C(G)}$
3. Cada subconjunto no vacío tiene vecinos en al menos componentes de . ${\displaystyle X\subseteq A(G)}$ ${\displaystyle |X|+1}$ ${\displaystyle D(G)}$
4. Cada coincidencia máxima en tiene la siguiente estructura: consiste en una coincidencia casi perfecta de cada componente de , una coincidencia perfecta de , y aristas de todos los vértices en con componentes distintos de . ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle C(G)}$ ${\displaystyle A(G)}$ ${\displaystyle D(G)}$
5. Si tiene componentes, entonces el número de aristas en cualquier coincidencia máxima es . ${\displaystyle D(G)}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle {\frac {1}{2}}(|V(G)|-k+|A(G)|)}$

Construcción

La descomposición de Gallai-Edmonds de un grafo se puede encontrar, de manera algo ineficiente, comenzando con cualquier algoritmo para encontrar una coincidencia máxima. A partir de la definición, un vértice está en si y solo si (el grafo obtenido de eliminando ) tiene una coincidencia máxima del mismo tamaño que . Por lo tanto, podemos identificar calculando una coincidencia máxima en y en para cada vértice . El complemento de se puede dividir en y directamente a partir de la definición. ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle D(G)}$ ${\displaystyle G-v}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle G}$ ${\displaystyle G-v}$ ${\displaystyle v}$ ${\displaystyle D(G)}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$

Un método particular para encontrar una coincidencia máxima en un gráfico es el algoritmo Blossom de Edmonds , y el procesamiento realizado por este algoritmo nos permite encontrar la descomposición de Gallai-Edmonds directamente.

Para encontrar una correspondencia máxima en un grafo , el algoritmo Blossom comienza con una correspondencia pequeña y pasa por múltiples iteraciones en las que aumenta el tamaño de la correspondencia en una arista. Podemos encontrar la descomposición de Gallai-Edmonds a partir del trabajo del algoritmo Blossom en la última iteración: el trabajo realizado cuando tiene una correspondencia máxima , que no puede hacer más grande. ${\displaystyle G}$ ${\displaystyle M}$

En cada iteración, el algoritmo Blossom pasa de grafos a grafos más pequeños contrayendo subgrafos llamados "Blossoms" a vértices individuales. Cuando esto se hace en la última iteración, los Blossoms tienen una propiedad especial: ${\displaystyle G}$

1. Todos los vértices de una flor son vértices no esenciales del gráfico más grande.
2. El vértice formado al contraer la flor es un vértice no esencial del grafo más pequeño.

La primera propiedad se desprende del algoritmo: cada vértice de una flor es el punto final de un camino alterno que comienza en un vértice descubierto por la coincidencia. La segunda propiedad se desprende de la primera por el siguiente lema: ^[6]

Sea un grafo, un coincidente en , y sea un ciclo de longitud que contiene aristas de y es disjunto en vértices con el resto de . Construya un nuevo grafo de mediante la reducción a un único vértice. Entonces es un coincidente máximo en si y solo si es un coincidente máximo en . ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle 2k+1}$ ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle G'}$ ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle M'=M-E(Z)}$ ${\displaystyle G'}$ ${\displaystyle M}$ ${\displaystyle G}$

Este lema también implica que cuando una flor se contrae, el conjunto de vértices no esenciales fuera de la flor permanece igual.

Una vez que el algoritmo ha contraído cada flor, el resultado es un grafo más pequeño , una coincidencia máxima en del mismo tamaño que , y un bosque alterno en con respecto a . En , la descomposición de Gallai-Edmonds tiene una breve descripción. Los vértices en se clasifican en vértices internos (vértices a una distancia impar en desde una raíz) y vértices externos (vértices a una distancia par en desde una raíz); es exactamente el conjunto de vértices internos, y es exactamente el conjunto de vértices externos. Los vértices de que no tienen la forma . ^[7] ${\displaystyle G'}$ ${\displaystyle M'}$ ${\displaystyle G'}$ ${\displaystyle M}$ ${\displaystyle F'}$ ${\displaystyle G'}$ ${\displaystyle M'}$ ${\displaystyle G'}$ ${\displaystyle F'}$ ${\displaystyle F'}$ ${\displaystyle F'}$ ${\displaystyle A(G')}$ ${\displaystyle D(G')}$ ${\displaystyle G'}$ ${\displaystyle F'}$ ${\displaystyle C(G')}$

La contracción de las flores preserva el conjunto de vértices no esenciales; por lo tanto, se puede encontrar a partir de tomando todos los vértices de que se contrajeron como parte de una flor, así como todos los vértices en . Los vértices en y nunca se contraen; y . ${\displaystyle D(G)}$ ${\displaystyle D(G')}$ ${\displaystyle G}$ ${\displaystyle D(G')}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle A(G)=A(G')}$ ${\displaystyle C(G)=C(G')}$

Generalizaciones

La descomposición de Gallai-Edmonds es una generalización de la descomposición de Dulmage-Mendelsohn de gráficos bipartitos a gráficos generales. ^[8]

Katarzyna Paluch ofrece una extensión del teorema de descomposición de Gallai-Edmonds a los emparejamientos de múltiples aristas en "Capacitated Rank-Maximal Matchings". ^[9]

Referencias

1. Gallai, Tibor (1963), "Kritische graphen II", Magyar Tud. Akád. Estera. Aeropuerto Internacional de Kutato. Kozl. , 8 : 373–395
2. Gallai, Tibor (1964), "Maximale Systeme unabhängiger Kanten", Magyar Tud. Akád. Estera. Aeropuerto Internacional de Kutato. Kozl. , 9 : 401–413
3. Edmonds, Jack (1965), "Caminos, árboles y flores", Revista Canadiense de Matemáticas , 17 : 449–467, doi : 10.4153/CJM-1965-045-4 , S2CID  18909734
4. Lovász, László ; Plummer, Michael D. (1986), Matching Theory (1ª ed.), Holanda Septentrional, Sección 3.2, ISBN 978-0-8218-4759-6
5. Teorema 3.2.1 en Lovász y Plummer, p. 94
6. Lema 9.1.1 en Lovász y Plummer, p. 358
7. Ejercicio 9.1.2 en Lovász y Plummer, p. 360
8. Szabó, Jácint; Loebl, Martin; Janata, Marek (14 de febrero de 2005), "La descomposición de Edmonds-Gallai para el problema de empaquetamiento de k piezas", The Electronic Journal of Combinatorics , 12 , doi : 10.37236/1905 , S2CID  11992200
9. Paluch, Katarzyna (22 de mayo de 2013), "Capacitated Rank-Maximal Matchings", Algorithms and Complexity , Notas de clase en informática, vol. 7878, Springer, Berlín, Heidelberg, págs. 324-335, doi :10.1007/978-3-642-38233-8_27, ISBN 978-3-642-38232-1