subgrafo conectado mínimo que contiene un conjunto dado de nodos

Question

I tiene un gráfico de no ponderado, conectado. Quiero encontrar un subgrafo conectado que sin duda incluye un cierto conjunto de nodos, y como algunos extras como sea posible. ¿Cómo podría esto ser realizado?

Por si acaso, voy a reformular la pregunta utilizando un lenguaje más preciso. Sea G (V, E) sea un no dirigida, el gráfico no ponderado, conectado. Sea N algún subconjunto de V. ¿Cuál es la mejor manera de encontrar el subgrafo conectado más pequeño G '(V', E ') de G (V, E) tal que N es un subconjunto de V'?

Las aproximaciones están bien.

Answer 1

No se puede pensar en un algoritmo eficiente para encontrar la solución óptima, pero suponiendo que el gráfico de entrada es denso, el siguiente podría funcionar bastante bien:

1. Convertir su G(V, E) gráfico de entrada a un G'(N, D) grafo ponderado, donde N es el subconjunto de vértices que desea cubrir y se D distancias (longitudes de trayectoria) entre los vértices correspondientes en el gráfico original. Esto le "colapso" todos los vértices que no es necesario en los bordes.

2. Se calcula el árbol de expansión mínima para G'.

3. "Ampliar" árbol de expansión mínima mediante el siguiente procedimiento: por cada d ventaja en el árbol de expansión mínimo, tomar el camino que corresponde en G gráfico y añadir todos los vértices (incluyendo los puntos finales) en el camino hacia el conjunto de resultados V' y todos los bordes en la ruta a la E' conjunto de resultados.

Este algoritmo es fácil de viaje para dar soluciones subóptimas. Ejemplo de caso: triángulo equilátero donde hay vértices en las esquinas, en los puntos medios de los lados y en el centro del triángulo, y los bordes a lo largo de los lados y desde las esquinas hacia el centro del triángulo. Para cubrir las esquinas es suficiente para recoger el punto medio del triángulo sola, pero este algoritmo podría escoger los lados. No obstante, si el grafo es denso, que debería funcionar bien.

Answer 2

Este es exactamente el conocido Steiner árbol . Sin más detalles sobre lo que sus casos se parecen, es difícil dar consejos sobre un algoritmo apropiado.

Answer 3

Las soluciones más fáciles será el siguiente:

a) sobre la base de MST: - inicialmente, todos los nodos de V están en V' - construir un árbol de expansión mínima de la gráfica G (V, E) - llamarlo T.
- bucle:. Por cada hoja de v en T que no es en N, v borrado de V'
- bucle de repetición hasta que todas las hojas en T están en N.

b) otra solución es la siguiente: - sobre la base de más corta del árbol caminos
. - recoger cualquier nodo N, lo llaman V, sea v una raíz de un árbol T = {v}. - Retirar de N. v

• bucle: 1) seleccionar la ruta más corta desde cualquier nodo de T y cualquier nodo de la ruta más corta N. t: {v, ..., u} donde v está en T y u es en N. 2) todos los nodos de p se añade a V'. 3) cada nodo en p y en N se elimina de N. --- repetición bucle hasta que N está vacía.

Al comienzo del algoritmo de: calcular todos los caminos más cortos en G utilizando cualquier algoritmo eficiente conocido.

En lo personal, he utilizado este algoritmo en una de mis papeles, pero es más adecuado para entornos distribuidos. Sea N el conjunto de nodos que necesitamos interconexión. Queremos construir un mínimo está conectado hablaba del conjunto de la gráfica G, y queremos dar prioridad a los nodos de N. Damos a cada nodo u a Identificación del identificador único (u). Dejamos que w (u) = 0 si u es en N, de lo contrario w (1). Creamos par (w (u), id (u)) para cada nodo u.

• cada nodo u construye un nodo de retransmisión conjunto múltiple. Esto es, un conjunto M (u) de neigbhors 1-hop tales que cada vecino 2-hop es un vecino a al menos un nodo en M (u). [El mínimo M (u), mejor es la solución].

• u es en V' si y sólo si: u tiene el par más pequeño (w (u), ID (u)) entre todos sus vecinos. o U se selecciona en el M (v), donde v es un vecino 1-hop de u con la más pequeña (w (u), id (u)).

- el truco cuando se ejecuta este algoritmo de forma centralizada, para ser eficaz en el cálculo de los vecinos 2-hop. Lo mejor que podía obtener de O (n ^ 3) es O (n ^ 2.37) por la multiplicación de matrices.

-. Realmente me gustaría saber cuál es la ración aproximación de esta última solución

Me gusta esta referencia para la heurística de árbol de Steiner: El Árbol de Steiner, Hwang Frank; Richards Dana 1955- invierno Pawel 1952

Answer 4

Se podría tratar de hacer lo siguiente:

1. Creación de un mínimo vértice de la cubierta para la N nodos deseada.

2. Contraer éstos, posiblemente no relacionadas, sub-gráficos en nodos "grandes". Es decir, para cada sub-gráfico, eliminarlo de la gráfica, y sustituirlo por un nuevo nodo. Llamar a este conjunto de nodos N'.

3. do un vértice-cobertura mínima de los nodos en N'.

4. "Desempaquetar" los nodos en N'.

No está seguro de si es o no le da una aproximación dentro de algún específico unido más o menos. Usted tal vez incluso podría engañar al algoritmo para tomar algunas decisiones muy estúpidas.