Supongamos que hay 3 nodos objetivo en un gráfico.¿Cómo encontrar todas las rutas vertex-disjoint en un gráfico?
Una ruta de vertex-disjoint significa que no hay ningún nodo, excepto los nodos finales durante la ruta.
Para un solo nodo, digamos el nodo i, ¿cómo encontrar todas las rutas vértice-disjuntas del nodo i a los tres nodos objetivo?
Puede resolver este problema reduciéndolo a un problema de flujo máximo en un gráfico construido apropiadamente. La idea es la siguiente:
La idea detrás de esta construcción es la siguiente. Cualquier ruta de flujo desde el nodo de inicio s al nodo de destino t debe tener una capacidad, ya que todos los bordes tienen capacidad uno. Como todas las capacidades son integrales, existe un flujo máximo integral. No pueden pasar dos rutas de flujo a través del mismo nodo intermediario, porque al pasar por un nodo en el gráfico, la ruta de flujo debe cruzar el borde desde v en hasta v en, y la capacidad aquí se ha restringido a una. Además, esta ruta de flujo debe llegar a t finalizando en uno de los tres nodos especiales que ha identificado, y luego siguiendo el borde desde ese nodo hasta t. Así, cada trayectoria de flujo representa una ruta nodo-disjunta de la fuente nodo s a uno de los tres nodos de destino. En consecuencia, calcular un flujo máximo aquí corresponde a encontrar el número máximo de rutas de nodo-disjunto que puede tomar desde s a cualquiera de los tres destinos.
Espero que esto ayude!
Tal vez mi expresión abt vertex-disjoint no es lo suficientemente clara. Para los nodos y el nodo t, hay una ruta s-> a-> b-> c-> d-> t, también hay otra ruta que comienza desde s como s-> e-> f-> g-> h -> t. En este caso, esta es una ruta vertex-disjoint. Pero si hay un camino como s-> e-> f-> g-> d-> t, este no es un vértice disjunto. – datcn
@templatetypedef Esa es una muy buena explicación. Gracias ! – ggauravr
¿Cuál sería el tiempo de ejecución de esta solución? En M) ? – razshan
Para ser claros, quiere decir que una ruta que comienza en 'i', pasa por cada uno de los tres nodos de destino, y luego regresa a' i' sin repeticiones, excepto que los dos extremos son iguales. Además, ¿quieres encontrar todos esos caminos (como dices) o el camino más corto (como está etiquetado)? – Dougal
En mi propósito, quiero encontrar una ruta que comience con el nodo i y termine en el nodo objetivo, digamos el nodo z. Si hay más de una ruta, no debería haber los mismos nodos en estas rutas, excepto los nodos iy el nodo z. Espero encontrar todos estos caminos de i a z. – datcn
Oh, eso es muy diferente de lo que yo (y templatetypedef) entendí. Entonces, ¿quieres encontrar un conjunto de rutas de 'i' a' z' para que las rutas sean disjuntas? Existen potencialmente muchos de estos conjuntos (dependiendo de cuál de los caminos posibles elijas). Entonces, tal vez lo que quieres hacer es encontrar todas las rutas de 'i' a' z' (por ejemplo, búsqueda por ancho de banda) y luego procesarlas para encontrar un conjunto disjunto. Una manera fácil de hacer eso, que no encontrará el conjunto más grande de ese tipo ni nada: elija un camino del conjunto, elimine todos los demás caminos que intersecan ese camino, repita. – Dougal