Primero solucionemos el siguiente problema:
Dado un gráfico no dirigido y vértices S y T, ¿cuántos caminos de vértices disjuntos existen de S a T?
Por ejemplo, en este gráfico, dos caminos disjuntos de S a T están marcados en rojo (S-3-2-T) y azul (S-1-4-T). Tenga en cuenta que si hubiéramos elegido S-2-4-T como una de las rutas, habría sido imposible encontrar otra ruta separada de vértices.
Resolvemos esto reduciéndolo a un problema de flujo máximo. Haremos otro gráfico dirigido donde el flujo máximo es el número de caminos separados de vértices de S a T. Así es como se genera este nuevo gráfico: Asigne S como fuente y T como sumidero. Haga dos copias de cada vértice (llame a las copias del vértice u como Au y Bu). Agregaremos bordes en el nuevo gráfico de la siguiente manera:
- ¿Cuáles son las aplicaciones en tiempo real del árbol binario enhebrado?
- ¿Qué idioma debo aprender para el comercio de algoritmos?
- ¿Cuál sería un buen método o algoritmo para predecir el ganador de una carrera de caballos, dada una gran cantidad de información sobre las carreras de caballos?
- ¿Hay algún algoritmo de ordenación que funcione en el orden de n?
- Estoy buscando algunas clases que me darían consejos sobre el enfoque. ¿Debo tomar el diseño del sistema, el algoritmo o la preparación de la estructura de datos?
- Si hubo un borde entre S y T en el gráfico original, agregue un borde dirigido con capacidad 1 de S a T en el nuevo gráfico
- Para cada vértice u con un borde con S en el gráfico original, agregue un borde dirigido con capacidad 1 de S a Au en el nuevo gráfico
- Para cada vértice u con un borde con T en el gráfico original, agregue un borde dirigido con capacidad 1 de Bu a T en el nuevo gráfico
- Para cada par de vértices {u, v} con una arista en el gráfico original, agregue aristas dirigidas con capacidad 1 de Bu a Av y de Bv a Au
- Agregue un borde dirigido con capacidad 1 de Au a Bu para todos los u
Aquí está el gráfico modificado para el gráfico que se muestra arriba: 
Tenga en cuenta cómo se transforman los caminos. En particular, cada vértice u en la ruta da como resultado el uso del borde Au-> Bu, y esto asegura que ningún vértice sea parte de más de una ruta. Por lo tanto, es fácil ver que el flujo máximo de S a T en este gráfico le da el número máximo de caminos separados de vértices entre S y T en el gráfico original.
Ahora, ¿cómo reducimos el problema del mapa intergaláctico a esto? Simple. Agregue un nuevo vértice X y conéctelo a Naboo y Coruscant. Encontrar un camino de vértices disjuntos de Naboo a Tatooine a Coruscant es posible si y solo si el número de caminos de vértices disjuntos de Tatooine a X es exactamente 2. Use la reducción gráfica anterior y ya está.
