Mínimo de cortes para ponderado de los gráficos

Question

Supongo que este es un problema bastante estándar, pero parece que no puede encontrar una solución intuitiva.

Tengo un grafo grafo ponderado $G = (V,E,f)$ con vértices $V$, bordes $E$ $f$ la función de ponderación de un borde.

Tengo un set $\mathbf{I} = \{ I_1, ..., I_n \}$ tal que para $I \in \mathbf{I}$, $I \subset V$.

Quiero realizar un mínimo de corte tipo de operación $G$ a producir $G'$ de manera tal que ningún par de vértices de un conjunto $I \in \mathbf{I}$ son accesibles desde cada uno de los otros, y de tal manera que el corte minimiza la suma de borde de pesos eliminado.

Como usted puede decir, yo no soy un asistente de matemáticas, pero necesito hacer esto para pequeños gráficos. (Preferiblemente en las próximas dos horas :/). Debo estar mirando algo como la programación lineal?

Los punteros sería muy apreciada. Gracias!

---

EDIT: No es una tarea problema (por desgracia)... si yo hubiera tenido el tipo de educación donde esta fue una tarea problema, yo no tendría que pedir ahora. :)

El fondo es que tengo un conjunto de las relaciones de equivalencia que se mantenga entre un conjunto de cosas. Puedo realizar el cierre transitivo de estos las relaciones de equivalencia para determinar clases de equivalencia.

Sin embargo, estas relaciones son falibles. Después, me puede mirar una clase de equivalencia $\{A, B, C, D, E\}$ y decir hey, una mierda!: cosa $A$ y lo $B$ son diferentes, y lo a $B$ $C$ son diferentes. Necesito romper esta clase de equivalencia.

Así, miro el original no transitiva gráfico de equivalencias. Me quiero hacer un corte mínimo, pero en general el número de vértices en el grafo son pequeños, y los lazos que se producen con frecuencia. Quiero evitar trivial decisiones en lo que a corte. Resulta que yo peso de la original de las relaciones de equivalencia.

Dada la original no transitiva grafo ponderado de equivalencias, y el conjunto de conjuntos de cosas que yo sé que es diferente, quiero realizar un mínimo de corte de la gráfica y, a continuación, volver a aplicar la clausura transitiva sobre el sub-gráficos.

Cualquier ayuda apreciada por un sueño Java hacker (incluso si no te gusta Java hackers).

Answer 1

Por lo que desea encontrar un coste mínimo de corte de manera que para cada $I \in \mathbf{I}$, $I$ es "cortar" por el conjunto de aristas?

En general, esto es NP-Duro, incluso en el caso de cada una de las $|I| = 2$ (i.e cada uno de ellos tiene exactamente dos elementos). (Creo que se llama como el multi-cut problema).

Al $\mathbf{I} = \{ \{s, t\}\}$, esto se convierte en el máximo flujo de min-cut problema que tiene solución en el polinomio de tiempo.

Espero que ayude.

Answer 2

No una respuesta a mi pregunta, como oposición a una solución que he aplicado en mi caso.

En primer lugar, en mi caso en particular, todos los $\lvert I \rvert = 2$ todos los $I \in \mathbf{I}$.

Bosquejar, he aplicado los siguientes:

• modelo el grafo ponderado de no transitiva, simétrica (sin dirección) equivalencias;
• aplicar iteraciones hasta que punto fijo de la siguiente manera:
  • el fin de los bordes basada en el borde de peso (se supone un orden total, y granular ordenar de tal manera que usted no tiene que hacer trivial decisiones entre iguales de pesos);
  • iterar a través de las aristas en orden decreciente, y se derivan de una "fuerte, transitiva de equivalencia" para la más alta ponderado de borde:
    • combinación de los nodos del grafo, y sus bordes y el borde de pesos;
    • no combinar los nodos que están en conflicto con $\mathbf{I}$;
    • no combinar nodos que ya han sido implicados en una combinación en la que la iteración.

De nuevo, esto no es precisamente una respuesta a mi pregunta, pero la idea central es la reconstrucción de las equivalencias en orden decreciente de borde de pesos, evitando cualquier tipo de equivalencias que se podría equiparar dos identificadores conocidos a ser diferente. Usted podría no acabar con un "mínimo de corte", pero es bastante intuitivo, fácil solución (que espero que tenga sentido).