Coincidencia de peso máximo

El emparejamiento de peso máximo es un problema de optimización en teoría de grafos cuyo objetivo es encontrar un emparejamiento con el máximo peso total posible en un grafo ponderado por aristas . Un emparejamiento es un conjunto de aristas independientes (es decir, un conjunto de aristas cuyos miembros no comparten un extremo común). El peso de un emparejamiento es la suma de los pesos de sus aristas.

Este problema es una generalización del problema de emparejamiento de cardinalidad máxima, ya que permite que las aristas tengan pesos numéricos arbitrarios. Cuando todos los pesos de las aristas son iguales, un emparejamiento de peso máximo es equivalente a un emparejamiento de cardinalidad máxima.

El problema de emparejamiento de peso máximo se puede resolver en tiempo polinomial utilizando, por ejemplo, el${\displaystyle O(EV^{2})}$algoritmo de floración , o el de Gabow${\displaystyle O(V^{3})}$algoritmo. ^{[ 1 ]} Esto contrasta con el problema de calcular el conjunto independiente máximo (ponderado) de vértices en un grafo, que es NP-difícil .

Ajustando los pesos de las aristas, los algoritmos para el problema de emparejamiento de peso máximo también pueden utilizarse para resolver el problema de emparejamiento de cardinalidad máxima y peso máximo, cuyo objetivo es encontrar, entre todos los emparejamientos de cardinalidad máxima, aquel cuyo peso total sea máximo. Ideas similares pueden utilizarse para resolver el problema de emparejamiento de cardinalidad máxima y peso mínimo . En los casos en que el grafo ponderado por aristas es bipartito , estos problemas también se conocen como el problema de asignación .

Dado un grafo no dirigido${\displaystyle G=(V,E,w)}$con conjunto de vértices${\displaystyle V}$, conjunto de bordes${\displaystyle E}$y función de peso${\displaystyle w:E\to \mathbb {R} }$, un emparejamiento de peso máximo es un conjunto independiente de aristas${\displaystyle M\subseteq E}$que maximiza el peso total

${\displaystyle w(M)=\sum _{e\in M}w(e).}$

Los pesos de los bordes pueden ser positivos, negativos o mixtos.

Una variante común de este problema consiste en calcular un emparejamiento que contenga la mayor cantidad de aristas posible. El peso total del emparejamiento se utiliza entonces como medida secundaria.

Para resolver el problema de emparejamiento de cardinalidad máxima y peso máximo en${\displaystyle G=(V,E,w)}$, un nuevo gráfico${\displaystyle G'=(V,E,w')}$se forma en la que, para cada borde${\displaystyle e\in E}$,

${\displaystyle w'(e)=C+w(e),}$

dónde${\displaystyle C}$es una constante positiva apropiada. Un emparejamiento de peso máximo en${\displaystyle G'}$entonces corresponde a un emparejamiento de cardinalidad máxima y peso máximo en${\displaystyle G}$.

Para resolver el problema de emparejamiento de peso mínimo de cardinalidad máxima , establezca

${\displaystyle w'(e)=Cw(e).}$

Nuevamente, una coincidencia de peso máximo en${\displaystyle G'}$produce una cardinalidad máxima y un peso mínimo de coincidencia en${\displaystyle G}$.

En ambos casos, una constante${\displaystyle C}$es necesario forzar al algoritmo a favorecer los emparejamientos con mayor cardinalidad independientemente de los pesos de las aristas en${\displaystyle G}$Cualquier valor de

${\displaystyle C>2\sum _ {e\in E}|w(e)|}$

es suficiente para este propósito.

El problema de emparejamiento de peso máximo se puede resolver en tiempo polinomial. Algunos algoritmos conocidos son:

• El${\displaystyle O(EV^{2})}$algoritmo de floración , introducido por Jack Edmonds en 1965 y posteriormente extendido para emparejamientos ponderados. Su complejidad también se mejoró posteriormente a${\displaystyle O(EV+V^{2}\log V)}$. ^{[ 2 ]}
• El${\displaystyle O(V^{3})}$algoritmo de Harold Gabow , que utiliza colas de prioridad y estructuras de árbol. ^{[ 1 ]}
• El${\displaystyle O(V^{3})}$Algoritmo húngaro , que resuelve el problema de emparejamiento de cardinalidad máxima y peso máximo únicamente en grafos bipartitos.

Otros algoritmos son revisados ​​por Duan y Pettie. ^{[ 3 ]} Su trabajo también propone un algoritmo de aproximación para grafos generales que se ejecuta en tiempo lineal para cualquier límite de error fijo.

Existen implementaciones eficientes disponibles en varias bibliotecas de software, entre ellas NetworkX , LEDA y la biblioteca de gráficos LEMON .

Los emparejamientos de peso máximo (y sus variantes de cardinalidad máxima) surgen en una amplia gama de escenarios de optimización.

• En el algoritmo de aproximación de Christofides para el problema del viajante , se utilizan emparejamientos de cardinalidad máxima y coste mínimo . En instancias del problema donde los pesos de las aristas forman un espacio métrico, este algoritmo garantiza costes de solución que no superan en más de un 50 % el coste óptimo.
• Los problemas que implican la asignación de recursos a entidades pueden modelarse como problemas de emparejamiento de peso máximo en grafos bipartitos , donde los pesos de las aristas reflejan la conveniencia de determinadas asignaciones. Algunos ejemplos son la asignación de trabajadores a tareas, muestras de sangre a pacientes, taxis a clientes en espera y vendedores a compradores.
• Los emparejamientos de cardinalidad máxima y costo mínimo se utilizan para resolver varios tipos de problemas de empaquetamiento ; particularmente aquellos que requieren la identificación de secuencias óptimas de artículos. ^{[ 4 ]}
• En bioinformática, el problema de emparejamiento de peso máximo se utiliza para analizar la interacción proteína-proteína . En este caso, las interacciones proteicas dentro de un organismo se modelan como un grafo ponderado por aristas, donde los vértices representan proteínas individuales y los pesos de las aristas representan la confianza en que sus interacciones sean biológicamente relevantes. El objetivo es identificar subgrafos densamente conectados dentro del grafo, ya que es probable que estos correspondan a complejos proteicos estables que funcionan como una unidad dentro de las células. ^{[ 5 ]}
• Los emparejamientos de cardinalidad máxima y coste mínimo se utilizan para resolver el problema del cartero chino , que consiste en encontrar un recorrido de peso mínimo que visite cada arista de un grafo ponderado al menos una vez.

• Emparejamiento (teoría de grafos)
• Coincidencia de cardinalidad máxima
• Problema de asignación
• Algoritmo Blossom

• Implementación del algoritmo en NetworkX