algorithm - grafos - Partida bipartita ponderada máxima dirigida que permite compartir vértices de inicio/final

matching grafos

Question

Sea G (U u V, E) un gráfico bipartito dirigido ponderado (es decir, U y V son los dos conjuntos de nodos del gráfico bipartito y E contiene los bordes ponderados dirigidos de U a V o de V a U). Aquí hay un ejemplo:

En este caso:

U = {A,B,C} 
V = {D,E,F} 
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)} 

Definición: DirectionalMatching (inventé este término solo para aclarar las cosas): conjunto de bordes dirigidos que pueden compartir los vértices de inicio o fin. Es decir, si U-> V y U ''-> V'' pertenecen a una Trama Direccional, entonces V / = U ''y V'' / = U pero puede ser que U = U ''o V = V''.

Mi pregunta: ¿Cómo encontrar eficientemente un Trazado Direccional , como se definió anteriormente, para un gráfico bipartito ponderado direccional que maximiza la suma de los pesos de sus bordes?

De manera eficiente , me refiero a la complejidad polinómica o más rápida, ya sé cómo implementar un enfoque ingenuo de fuerza bruta.

En el ejemplo anterior, la combinación direccional máxima ponderada es: {F-> A, C-> E, B-> D}, con un valor de 13.

Demostrar formalmente la equivalencia de este problema a cualquier otro problema bien conocido en la teoría de grafos también sería valioso.

¡Gracias!

Nota 1: Esta pregunta se basa en la coincidencia bipartita máxima ponderada _con_ bordes dirigidos, pero con la relajación adicional que se permite para que los bordes de la coincidencia compartan el origen o el destino. Dado que esa relajación hace una gran diferencia, creé una pregunta independiente.

Nota 2: Esta es una coincidencia de peso máxima. La cardinalidad (cuántos bordes están presentes) y el número de vértices cubiertos por la coincidencia es irrelevante para un resultado correcto. Solo el peso máximo importa.

Nota 2: Durante mi investigación para resolver el problema que encontré en este documento, creo que sería útil para otros que intentan encontrar una solución: Ciclos y trayectorias alternas en multigrafos de colores de borde: una encuesta

Nota 3: en caso de que ayude, también puede pensar en el gráfico como su equivalente multigrafía bi-direccional no dirigida de 2 bordes. La formulación del problema se convertiría en: Encontrar el conjunto de bordes sin trayectorias alternas de color o ciclos que tiene una suma de peso máxima.

Nota 4: sospecho que el problema podría ser NP-hard, pero no tengo tanta experiencia con las reducciones, así que no he podido probarlo todavía.

Otro ejemplo más :

Imagina que tuviste

4 vértices: {u1, u2} {v1, v2}

4 bordes: {u1->v1, u1->v2, u2->v1, v2->u2}

Entonces, independientemente de sus ponderaciones, u1->v2 y v2->u2 no pueden estar en la misma v2->u2 direccional , tampoco pueden v2->u2 u2->v1 y u2->v1 . Sin embargo, u1->v1 y u1->v2 pueden, y también pueden u1->v1 y u2->v1 .

Answer 1

Defina un nuevo gráfico no dirigido G'' desde G siguiente manera.

1. G'' tiene un nodo (A, B) con un peso w para cada borde dirigido (A, B) con un peso w en G
2. G'' tiene borde no dirigido ((A, B),(B, C)) si (A, B) y (B, C) son ambos bordes dirigidos en G

http://en.wikipedia.org/wiki/Line_graph#Line_digraphs

Ahora encuentre un vértice independiente máximo (ponderado) establecido en G'' .

http://en.wikipedia.org/wiki/Vertex_independent_set

Editar: las cosas después de este punto solo funcionan si todos los pesos de borde son los mismos: cuando los pesos de borde tienen valores diferentes, es un problema más difícil (google "conjunto de vértices independientes de peso máximo" para posibles algoritmos)

Típicamente esto sería un problema NP-difícil. Sin embargo, G'' es un gráfico bipartito, contiene solo ciclos pares. Encontrar el máximo vértice independiente (ponderado) establecido en un gráfico bipartito no es NP-difícil.

El algoritmo que ejecutará en G'' es el siguiente.

1. Encuentre los componentes conectados de G'' , digamos H_1, H_2, ..., H_k
2. Para cada H_i haga un 2-coloreado (digamos rojo y azul) de los nodos. El enfoque del libro de cocina aquí es hacer una búsqueda de profundidad en H_i alternar colores. Un enfoque simple sería colorear cada vértice en H_i en función de si el borde correspondiente en G va de U a V (rojo) o de V a U (azul).
3. Las dos opciones para las cuales los nodos para seleccionar de H_i son todos los nodos rojos o todos los nodos azules. Elija el nodo de color configurado con mayor peso. Por ejemplo, el conjunto de nodos rojos tiene un peso igual a H_i.nodes.where(node => node.color == red).sum(node => node.w) . Llame al nodo de mayor peso establecido N_i .
4. Su conjunto máximo de vértices ponderado máximo ahora es union(N_1, N_2, ..., N_k) .

Como cada vértice en G'' corresponde a uno de los bordes dirigidos en G , tienes tu Mapeo Direccional máximo.

Answer 2

Este problema se puede resolver en tiempo polinomial utilizando el algoritmo húngaro . La "prueba" de Vor anterior es incorrecta.

El método de estructurar el problema para el ejemplo anterior es el siguiente:

   D E F
A  # 7 9  
B  1 # #
C  # 3 #

donde "#" significa infinito negativo. A continuación, resuelve la matriz utilizando el algoritmo húngaro para determinar la coincidencia máxima. Puede multiplicar los números por -1 si quiere encontrar una coincidencia mínima.