Como extraer de un grafo un subconjunto conectado (relaciones de tablas)

[mamcx]

Bueno, primero que todo un aplauso por la investigacion (que desparche hacer esos grafos a punta de ASCII Art!).


Pienso que el problema se parte en 2, y solo la primera parte es la dificil para mi.

El problema es:

1- Como, a partir de un numero N de nodos saco los nodo adyacentes que son necesarios para sacar un subgrafo conectado
2- Cual es la ruta mas optima entre un nodo x y uno y. Esa es muy facil y la tengo resuelta.

Imagina en tu grafica que selecciono a 1 y 5. Hay dos caminos posibles, uno mas largo que otro. Lo unico que deseo es tener ambos caminos, que usando el algoritmo de ruta corta saco cual es la mas efectiva entre 1 y 5.

No te preocupes por los pesos... pero si es necesario preocuparse, digamos que le pongo peso 1 a las maestras, 2 a las de movimiento. O 1 a las relaciones 1-1 y 2 a las 1-muchos.