Borde de máxima compatibilidad

En teoría de grafos , una arista de máxima coincidencia en un gráfico es una arista que está incluida en al menos una coincidencia de cardinalidad máxima en el gráfico. ^[1] Se permite un término alternativo borde . ^{[2] [3]}

Un problema fundamental en la teoría de coincidencias es: dado un gráfico G , encontrar el conjunto de todas las aristas máximamente coincidentes en G. Esto es equivalente a encontrar la unión de todas las coincidencias máximas en G (esto es diferente al problema más simple de encontrar un único máximo) . coincidente en G ). Se conocen varios algoritmos para este problema.

Motivación

Considere una agencia de búsqueda de pareja con un grupo de hombres y mujeres. Dadas las preferencias de los candidatos, la agencia construye un gráfico bipartito donde existe una ventaja entre un hombre y una mujer si son compatibles. El objetivo final de la agencia es crear tantas parejas compatibles como sea posible, es decir, encontrar una coincidencia de máxima cardinalidad en este gráfico. Para lograr este objetivo, la agencia primero elige una arista en el gráfico y sugiere al hombre y a la mujer en ambos extremos de la arista que se encuentren. Ahora, la agencia debe tener cuidado de elegir sólo una ventaja con la máxima compatibilidad. Esto se debe a que, si elige una arista que no se puede emparejar al máximo, puede quedarse atascado con una arista que no se puede completar hasta una coincidencia de cardinalidad máxima. ^[1]

Definición

Sea G = ( V , E ) un gráfico, donde V son los vértices y E son las aristas. Una coincidencia en G es un subconjunto M de E , tal que cada vértice en V es adyacente como máximo a un solo borde en M . Una coincidencia máxima es una coincidencia de máxima cardinalidad.

Una arista e en E se llama máximamente coincidente (o permitida ) si existe una coincidencia máxima M que contiene e .

Algoritmos para gráficos generales.

Actualmente, el algoritmo determinista para gráficos generales más conocido se ejecuta en el tiempo . ^[2] ${\displaystyle O(VE)}$

Existe un algoritmo aleatorio para gráficos generales en el tiempo . ^[4] ${\displaystyle {\tilde {O}}(V^{2.376})}$

Algoritmos para gráficos bipartitos

En gráficos bipartitos, si se conoce una única coincidencia de cardinalidad máxima , es posible encontrar todos los bordes máximamente coincidentes en tiempo lineal . ^[1] ${\displaystyle O(V+E)}$

Si no se conoce una coincidencia máxima, se puede encontrar mediante algoritmos existentes. En este caso, el tiempo de ejecución general resultante es para gráficos bipartitos generales y para gráficos bipartitos densos con . ${\displaystyle O(V^{1/2}E)}$ ${\displaystyle O((V/\log V)^{1/2}E)}$ ${\displaystyle E=\Theta (V^{2})}$

Gráficos bipartitos con una coincidencia perfecta.

El algoritmo para encontrar aristas de máxima coincidencia es más simple cuando el gráfico admite una coincidencia perfecta . ^{[1] : sub.2.1}

Sea la gráfica bipartita , donde y . Que sea la combinación perfecta . ${\displaystyle G=(X+Y,E)}$ ${\displaystyle X=(x_{1},\ldots ,x_{n})}$ ${\displaystyle Y=(y_{1},\ldots ,y_{n})}$ ${\displaystyle M=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}}$

Teorema: una arista e es máximamente compatible si y solo si e se incluye en algún ciclo de alternancia M , un ciclo que alterna entre aristas en M y aristas que no están en M. Prueba :

• Si e está en un ciclo alterno, entonces e está en M o, al invertir el ciclo, obtenemos una nueva coincidencia perfecta que contiene e . Por lo tanto, e es máximamente emparejable.
• Por el contrario, si e es máximamente emparejable , entonces se encuentra en alguna coincidencia perfecta N. Al tomar la diferencia simétrica de M y N, podemos construir un ciclo alterno que contenga e .

Ahora, considere un gráfico dirigido , donde y hay una arista desde a en H si y solo hay una arista entre y en G (tenga en cuenta que, suponiendo que dichas aristas no están en M ). Cada M ciclo alterno en G corresponde a un ciclo dirigido en H. Un borde dirigido pertenece a un ciclo dirigido si ambos puntos finales pertenecen al mismo componente fuertemente conectado . Existen algoritmos para encontrar todos los componentes fuertemente conectados en tiempo lineal. Por lo tanto, el conjunto de todas las aristas de máxima coincidencia se puede encontrar de la siguiente manera: ${\displaystyle H=(Z,E)}$ ${\displaystyle Z=(z_{1},\ldots ,z_{n})}$ ${\displaystyle z_{i}}$ ${\displaystyle z_{j}}$ ${\displaystyle i\neq j}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$

• Dado el gráfico bipartito no dirigido y la coincidencia perfecta M , marque cada borde en M como máximamente coincidente. ${\displaystyle G=(X+Y,E)}$ ${\displaystyle (x_{i},y_{i})}$
• Construya el gráfico dirigido como se muestra arriba. ${\displaystyle H=(Z,E)}$
• Encuentre todos los componentes fuertemente conectados en H.
• Para cada i , j que estén en el mismo componente, marque el borde como de máxima coincidencia. ${\displaystyle (z_{i},z_{j})}$ ${\displaystyle (x_{i},y_{j})}$
• Marque todos los bordes restantes como no coincidentes al máximo.

Gráficos bipartitos sin coincidencia perfecta

Sea la gráfica bipartita , donde y y . Sea la coincidencia máxima dada , donde . Los bordes en E se pueden clasificar en dos clases: ${\displaystyle G=(X+Y,E)}$ ${\displaystyle X=(x_{1},\ldots ,x_{n})}$ ${\displaystyle Y=(y_{1},\ldots ,y_{n'})}$ ${\displaystyle n\leq n'}$ ${\displaystyle M=\{(x_{1},y_{1}),\ldots ,(x_{t},y_{t})\}}$ ${\displaystyle t\leq n\leq n'}$

• Aristas con ambos puntos finales saturados por M . A estos bordes los llamamos M-superior .
• Aristas con exactamente un punto final saturado por M . A estos bordes los llamamos M-inferiores .
• Tenga en cuenta que no hay aristas con ambos puntos finales no saturados por M , ya que esto contradeciría la maximalidad de M .

Teorema: Todos los bordes inferiores son máximamente coincidentes. ^{[1] : sub.2.2} Prueba : supongamos donde está saturado y no. Luego, eliminando y sumando se obtiene una nueva coincidencia de cardinalidad máxima. ${\displaystyle M}$ ${\displaystyle e=(x_{i},y_{j})}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$ ${\displaystyle e=(x_{i},y_{j})}$ ${\displaystyle M}$ ${\displaystyle e=(x_{i},y_{j})}$

Por lo tanto, queda por encontrar los bordes con máxima compatibilidad entre los M superiores.

Sea H el subgrafo de G inducido por los M nodos saturados. Tenga en cuenta que M es una coincidencia perfecta en H. Por lo tanto, utilizando el algoritmo de la subsección anterior, es posible encontrar todas las aristas que sean máximamente coincidentes en H. Tassa ^[1] explica cómo encontrar los bordes restantes de máxima coincidencia, así como cómo actualizar dinámicamente el conjunto de bordes de máxima coincidencia cuando cambia el gráfico.

Referencias

1. Tassa, Tamir (16 de marzo de 2012). "Encontrar todos los bordes de máxima coincidencia en un gráfico bipartito". Informática Teórica . 423 : 50–58. doi : 10.1016/j.tcs.2011.12.071 . ISSN  0304-3975.
2. De Carvalho, Marcelo H.; Cheriyan, José (1 de octubre de 2005). "Un algoritmo para descomposiciones auditivas de gráficos cubiertos coincidentes". Transacciones ACM sobre algoritmos . 1 (2): 324–337. doi :10.1145/1103963.1103969. ISSN  1549-6325. ${\displaystyle O(VE)}$
3. Lovász, László; Plummer, Michael (18 de agosto de 2009). Teoría del emparejamiento . Providence, Rhode Island: Sociedad Matemática Estadounidense. doi :10.1090/chel/367. ISBN 9780821847596.
4. Rabin, Michael O.; Vazirani, Vijay V. (1989). "Máximos emparejamientos en gráficos generales mediante aleatorización" (PDF) . Revista de algoritmos . 10 (4): 557–567. doi :10.1016/0196-6774(89)90005-9..