Parte 2

[jalliende]

Hola, al ser grafos dirigidos si existe el arco(a,b) y el arco(b,a) entonces es un grafo cíclico o no?

[jalliende]

Una duda en la parte c, cuando nos piden eliminar arcos, los arcos a eliminar necesariamente deben formar parte de los ciclos? Por que podría ocurrir por ejemplo que el arco al eliminar el arco (a,b) se elimina un ciclo, pero al eliminar el arco (a,b) y el arco (a,c) también se elimina el ciclo pero no es necesario eliminar el arco (a,c) ya que solo con el arco (a,b) basta.

[jabaier]

Hola Joaquín.

Si existe el arco(a,b) y el arco(b,a) hay un ciclo en el grafo pues puedes hacer una caminata infinita entre a y b. Respecto a la segunda pregunta, no es necesario que impongas que los arcos a eliminar pertenezcan a un ciclo, tu programa debería deducir eso en forma automática.

Jorge

[jmwielandt]

tu programa debería deducir eso en forma automática.

@jabaier No me queda claro o al menos quiero asegurarme.

Si mi grafo es:

nodo(a).
nodo(b).
nodo(c).

arco(a,b).
arco(b,a).
arco(a,c).

Un posible modelo tendría:

eliminar(a,b) eliminar(a,c)

¿Eso está mal?

Notar que eliminar(a,c) no es necesario para que sea un dag.

Gracias :D

[jabaier]

Aunque no es necesario, la pregunta no exige que se entregue el mínimo número de arcos a eliminar. Por lo tanto, está correcto que resulte un modelo como el que describes.