costes perjudiciales mínimos en el gráfico

Question

se nos da un gráfico G (V, E) con N nodos (numeradas de 0 a N-1) y exactamente (N-1) bidireccional Bordes.

Cada borde en un gráfico tiene un costo positivo C (u, v) (Peso del borde).

El toda gráfico es tal que hay un camino único entre cualquier par de nodos.

También se nos da una Lista L del número de nodo, en el que se colocan las bombas.

Nuestro objetivo es daño/eliminar el borde partir de la gráfica tal, que después de dañino/eliminación de los bordes en el gráfico, no hay conexión entre las bombas -

que es después perjudicial, no hay camino entre dos bombas.

El costo de dañar el borde (u, v) =peso Edge (u, v).

Por lo tanto, tenemos que dañar esos bordes, por lo que el costo total de daño es mínimo.

Ejemplo:

Total Nodes=N=5 
Total Bomb=Size of List L=3 

List L={2,4,0}//Thats is at node number 2,4 and 0 bomb is placed... 

Total Edges =N-1=4 edges are:: 

u v Edge-Weight 

2 1 8 

1 0 5 

2 4 5 

1 3 4 



In this case the answer is :: 
Total Damaging cost =(Edge Weight (2,4) + Edge Weight(0,1)) 
      =5+5=10. 

So when we remove the edge connecting node (2,4), 
and the edge connecting node (0,1) ,there is no connection left 
between any pair of machines in List {2,4,0}; 

Note any other,combinations of edges(that we damaged) to achieve the 
target goal ,needs more than 10 unit cost. 

Constraints:: 
N(ie. Number of Nodes) <= 100,000 
ListSize |L|(ie. Number of Bombs) <= N 
1 <=Edge cost(u,v) <= 1000,000 

lo que había hecho?

Hasta ahora, no había encontrado ninguna manera eficiente :(.

Además, como el número de nodos es N, el número de aristas es exactamente N-1 y todo el gráfico es tal que hay un camino único entre cualquier par de nodos, llegué a una conclusión que la gráfica es una ÁRBOL.

traté de modificar el algoritmo de Kruskal pero eso no me ayudó tampoco.

¡Gracias!

Answer 1

Este es el problema del corte multidireccional en los árboles. Se puede resolver en tiempo polinomial mediante una programación dinámica directa. Ver Chopra y Rao: "On the multiway cut polyhedron", Redes 21 (1): 51-89, 1991.

Answer 2

Creo que un Kruskal modificado es el camino a seguir aquí.

Tome la gráfica G '= (V', E '), V' = V, E '= {}. Ordene los bordes en E en un orden de costo no creciente. Ahora, para cada borde en E, agréguelo a E si no conecta dos componentes que tienen vértices con bombas. El resultado es la suma de los costos de E-E '.

EDIT:

La ejecución de este en su ejemplo.

Inicialmente, nuestro conjunto de bordes está vacío {}, y tomamos los bordes ordenados en orden no creciente [(1, 2), (0, 1), (2, 4), (1, 3) ]

Por lo tanto, al principio, nuestro gráfico se compone de 5 componentes desconectados.

(1, 2) tiene un costo de 8, y solo uno de los componentes que conecta tiene una bomba. Entonces lo agregamos a E '. E '= {(1, 2)} y tenemos 4 componentes.

El siguiente límite de costo más alto es (0, 1) con un costo de 5. Pero ambos componentes tienen bombas, así que no agregue este borde.

El siguiente es (2, 4). Esto también se conecta a componentes con bombas, por lo que también omitimos esto.

Por último, el límite de costo más bajo es (1, 3). Como uno de sus componentes (que contiene solo el nodo 3) no tiene una bomba, lo agregamos a E '.

Esto nos da E '= {(1,2), (1, 3)}.

Mi razonamiento es que tratamos de agregar bordes con mayor costo antes que con un costo menor, lo que garantiza que en cualquier camino entre nodos con bombas en el nodo original, se agregarán todos menos el costo más bajo.

Answer 3

creo que la siguiente sugerencia debería funcionar:

• 1) Comience con una bomba, en su ejemplo empiezo con: 0
• 2) Crear rutas de la bruja de todos los nodos adyacentes. Entonces toma todas las relaciones y comienza un camino con ellas. En su ejemplo, comenzará una ruta: 0 -> 1.
• 3) Si golpea otra bomba en un camino, eliminará el borde con el costo más bajo. En el ejemplo, no golpeamos una bomba, entonces continuamos con el paso2.
• 3A) Aún no hay ninguna bomba en ningún camino. Continúe con el paso 2 y amplíe las rutas con los nuevos nodos adyacentes. En su caso, se creará una nueva ruta: 1 -> 3. Y el existente se extenderá: 0 -> 1 -> 2
• 3B) Se encuentra una bomba en el camino. Tome el camino donde se encuentra la bomba y elimine el borde con el costo más bajo. En su ejemplo, la ruta 0 -> 1 -> 2 contiene una bomba (2). Entonces eliminamos la relación con el costo 5. Elimine la ruta del 'todo' y continúe con el paso 2 en los últimos nodos alcanzados (2 y 3).

I final, debe atravesar cada nodo exactamente una vez. Si no me equivoco, la complejidad debe ser O (n log n)

Answer 4

Creo que esto se puede hacer en tiempo lineal.

Rootee el árbol en algún vértice y luego comience con un recorrido de abajo hacia arriba.

Comience con una hoja. Si no hay una bomba, corte la hoja y avance. Si hay una bomba, debe cortar un borde en el camino hacia esta hoja. Propagar información sobre el borde más barato para esta hoja.

Luego, cuando estás en el vértice interno, tienes estas posibilidades: Si hay una bomba en el vértice y algunas bombas debajo, corta las rutas más baratas hacia todas ellas. Si no hay una bomba y solo una bomba debajo, propague información sobre la ruta más barata. Si hay más bombas debajo, corte todas excepto una con la ruta más cara.

Answer 5

http://www.cs.ust.hk/mjg_lib/Classes/COMP572_Fall06/Notes/Tree_Multicut.ps

tiene una descripción del algoritmo.

Google HTML version del archivo PostScript

===================================== ====

http://dspace.mit.edu/bitstream/handle/1721.1/5394/OR-308-95.pdf?sequence=1

el caso k = 2 no es la instancia única polinomialmente resoluble del problema de corte de múltiples vías. Lovdsz [12] y Cherkasskij [3] muestran que cuando ce = 1 Ve E E y G es euleriano, entonces el problema de corte de múltiples vías es polinomialmente soluble. Erdos y Sz6kely [8] han demostrado que una generalización de el problema del corte de múltiples vías es polinomialmente soluble cuando el gráfico subyacente G es un árbol. Dalhaus et. Alabama. [7] han demostrado que el problema es polinomial solucionable para k fijo en gráficos planos.

que había escrito un simple solución basada algoritmo codicioso última noche, que consistió en la eliminación de nodos que no están en un camino entre dos nodos rojos (terminal), y luego seleccionando el nodo de peso más pequeño, y luego repetir el proceso en los subárboles. Lo eliminé porque una lectura posterior sugería que el problema es NP. Sin embargo, esta referencia sugiere que existe una solución polinómica ...

Answer 6

Aquí es mi hipótesis:

El Gráfico G es un árbol. Por lo tanto, solo hay una ruta entre dos nodos cualquiera.

Supongamos que hay L Red (de bomba) nodos y V-L blanco (nodos no de bomba). La solución requiere la partición de G en un bosque de subárboles L. Esto requiere la eliminación de un mínimo de L-1 bordes.

Cada uno de los bordes eliminados debe estar en una ruta entre dos nodos rojos.

A. Pode el árbol G para eliminar todos los bordes que no participan en una ruta entre dos nodos rojos.

1. eliminar nodos hoja blanca (y el borde incidente) de la consideración.
2. Repita el n. ° 1 hasta que no haya nodos de hoja blanca en el gráfico modificado.

B. Después de (A) todos los bordes izquierdo en la gráfica son los bordes que forman un camino entre dos nodos rojos.

Seleccione el borde con la menor peso en este árbol. Esto dará como resultado dos subárboles con cada árbol que contenga al menos un nodo Rojo.

C. volver al paso A para cada uno de los sub-árboles creados en B si contiene más de un nodo Red.

Esto es O (V log V) (| E | is | V | -1).