algorithm - maximum - matching grafos
Máxima coincidencia bipartita ponderada_con_ bordes dirigidos (1)
El comentario de dfb es correcto, para dos vértices A, B puedes descartar el más barato de los dos bordes AB y BA.
La prueba es de una sola línea:
Teorema: una coincidencia máxima M nunca contiene el borde más barato de AB y BA para dos vértices A, B cualquiera.
Prueba: Sea M una coincidencia máxima. Supongamos que AB está en M y es más barato que BA. Defina M ''= M - {AB} + {BA}. M ''es claramente una coincidencia, pero es más caro. Eso contradice la suposición de que M fue una coincidencia máxima.
Conozco varios algoritmos para calcular la correspondencia ponderada máxima de gráficos bipartitos ponderados y no dirigidos (es decir, el problema de asignación):
Por ejemplo ... El algoritmo húngaro, Bellman-Ford o incluso el algoritmo Blossom (que funciona para gráficos generales, es decir, no bipartitos).
Sin embargo, ¿cómo puedo calcular la coincidencia máxima ponderada si los bordes del gráfico bipartito son ponderados y dirigidos ?
Agradecería sugerencias sobre algoritmos con complejidad polinómica o transformaciones previas para hacer que el gráfico no esté dirigido, de modo que pueda aplicar cualquiera de los algoritmos antes mencionados.
Editar: tenga en cuenta que la coincidencia debe maximizar el peso de los bordes, es por eso que tener bordes dirigidos hace una diferencia (A-> B puede tener un peso totalmente diferente de B-> A).
Es cierto que si maximizara la cardinalidad, los bordes dirigidos no marcarían la diferencia y podría aplicar cualquiera de los algoritmos conocidos para maximizar la cardinalidad: Hopcroft-Karp, Maximum Network Flow ...
Edición 2 : dado que la coincidencia es un término que normalmente se aplica a los gráficos no dirigidos, permítanme aclarar lo que quiero decir exactamente al hacer coincidir en esta pregunta: un conjunto de bordes dirigidos que no comparten los vértices de inicio o fin . Más formalmente, si U-> V y U ''-> V'' son parte del emparejamiento, entonces V / = U ''y V'' / = U.