algorithm - karp - matching grafos
Gráfico bipartito máximo(1, n) "coincidencia" (1)
Tengo un gráfico bipartito. Estoy buscando un máximo (1, n) "coincidencia", lo que significa que cada vértice de la partición A tiene n vértices asociados de la partición B.
La siguiente figura muestra una coincidencia máxima (1,3) en un gráfico. Los bordes seleccionados para el emparejamiento son rojos y los bordes no seleccionados son negros.
Ver la figura http://www.freeimagehosting.net/uploads/9a8df2d97c.gif
Esto difiere del problema de correspondencia bipartita estándar en el que cada vértice está asociado con solo un otro vértice, que podría llamarse (1,1) coincidente con esta notación.
Si la cardinalidad correspondiente (n) no se impone pero es un límite superior (los vértices de A pueden tener 0 <x <= n vértices asociados de B), la correspondencia máxima se puede encontrar fácilmente transformando el gráfico en una red de flujo y encontrando el flujo máximo. Sin embargo, esto no garantiza que la cantidad máxima de vértices desde A tenga n pares asociados de B.
Esto es NP-hard, reducción del problema del conjunto independiente máximo. Para cualquier gráfico G puede construir (en tiempo polinomial) una instancia de su problema de tal manera que:
- Los vértices en A representan vértices de
G - Cada vértice de A está conectado a exactamente n vértices de B
- Dos vértices de A tienen un vecino común en B si y solo si están conectados en
GPara que esto sea siempre posible, elija n = Δ (G).
Ahora, la "coincidencia" máxima en la instancia vuelve al conjunto máximo independiente en G