Lo que debemos buscar es si el grafo es conexo.  Podemos elaborar 
diferentes estrategias para alcanzar dicho fin.

* Generar la partición de los vértices, de tal manera que todos los
  vértices con caminos que los unen pertenezcan a la misma partición. El
  algoritmo puede partir de los vértices unidos por arcos (caminos de
  longitud uno), y luego irá agregando los de longitud dos, etc. hasta
  que se llega la longitud n, con n la cantidad de vértices. (En
  realidad alcanzaría con el diámetro del grafo, que es la longitud del
  camino más largo.)  Luego si solamente hay una única partición,
  entonces el grafo es conexo.

* Verificar la definición de conexo dada en el enunciado.  Para esto 
  tomamos por turno cada vértice, y verificamos que haya un camino desde
  ese vértice hasta todos los demás.

Seguiremos la segunda estrategia en esta primera aproximación.

Representaremos con arista(x,y) a la existencia de una arista en A que
una los vértices x, e y que pertenecen a V.

Nuestra definición de grafo es la de un grafo no-dirigido.  Eso implica
que si existe arista(x,y) eso es equivalente a decir que existe
arista(y,x).  Desde el punto de un programa en Prolog esto tiene una 
implicancia peligrosa pues puede conducir a computaciones infinitas.  
Como el enunciado aclara específicamente que se debe describir la forma 
en que se representa el grafo, elegiremos una forma que sea la más 
económica de acuerdo al algoritmo elegido.

Elegiremos la representación (A) del ejercicio 5.

Los ejemplos se representarán entonces: (g1 no es conexo, g2 es conexo)

g1 = [ [a,b,c,d,h,m,t,w,x], 
       [ [a,m],[a,d],[a,c],[b,c],[b,h],[b,d],[c,d],[t,x],[w,x] ] ]

g2 = [ [a,b,c,d,h,m,t,w,x],
       [ [a,m],[a,d],[a,c],[b,c],[b,h],[b,d],[c,d],[t,x],[w,x],
         [h,t],[d,x] ] ]


Un grafo será conexo si al recorrer todos los vértices, cada uno de
ellos a su turno está conectado por caminos con todos los demás.  Esto
sugiere hacer un predicado que tome un vértice y determine si está
conectado a todos los demás vértices.  Para saber cuáles son los 
vértices con los cuales debe tratar, se le pasará una lista de vértices, 
y para encontrar los caminos, una lista de aristas.

Un grafo es conexo si todos sus vértices están conectados:

conexo([Vertices,Aristas]) :-
	todos_vertices_conectados(Vertices, Aristas).


Necesito un argumento para ir recorriendo recursivamente los vértices
como origen de caminos hasta explorarlos a todos (primer argumento) y
también necesito la lista de todos los vértices para usar como destino 
(segundo argumento).  Fabrico un predicado auxiliar para lograr esto:

todos_vertices_conectados(Vertices, Aristas) :-
	todos_vertices_conectados_aux(Vertices, Vertices, Aristas).


Cuando la lista se vació, eso significa que exploré con éxito todos los 
vértices, por lo tanto, salgo con éxito.

todos_vertices_conectados_aux([], _, _) :- !.


Para saber si todos los vértices están conectados, pruebo uno por uno 
con un predicado que toma un vértice como argumento y acierta si dicho 
vértice está conectado:

todos_vertices_conectados_aux([V|Vs], Vertices, Aristas) :-
	vertice_conectado(V, Vertices, Aristas),
	todos_vertices_conectados_aux(Vs, Vertices, Aristas).


Para saber si un vértice dado está conectado, busco que para cada otro 
vértice distinto de él, haya un camino que los una.

Si ya exploré todos los vértices, eso significa que el vértice dado está 
conectado con todos, y por lo tanto salgo con éxito:

vertice_conectado( _, [], _ ) :- !.


vertice_conectado( V1, [V2|Vs], Aristas ) :-
	camino(V1, V2, Aristas, _),
	vertice_conectado(V1, Vs, Aristas).




Para saber si hay un camino, lo genero en el último argumento de 
camino/4.

camino(V1, V2, Aristas, Camino) :-
	camino_sin_ciclos(V1, V2, Aristas, [], Camino).



Si hay una arista entre ellos, entonces hay un camino entre V1 y V2:

camino_sin_ciclos(V1, V2, Aristas, _, [V2,V1]) :-
	( member( [V1,V2], Aristas) ; member([V2,V1], Aristas) ), !.

Note como en la cláusula anterior hemos hecho uso del OR de Prolog que 
tiene la forma (;)/2 con el siguiente esqueleto:

	           ;(+callable_term, +callable_term)

donde al intentar satisfacer:

			meta1 ; meta2

se crea un punto de selección y se ejecuta meta1.  Cuando se produce el 
retroceso, se ejecutará meta2.


/* VerticesVisitados es el recorrido hasta ahora, que me
 * sirve para evitar hacer ciclos
 */
camino_sin_ciclos(V1, V2, Aristas, 
                  VerticesVisitados, [V1|Camino_Z_V2]) 3:-
	( member( [V1,Z], Aristas) ; member( [Z,V1], Aristas) ),
	\+(member(Z, VerticesVisitados)),
	camino_sin_ciclos(Z, V2, Aristas, [V1|VerticesVisitados], 
                          Camino_Z_V2).


El predicado \+/1 es el not/1 en el estándar ISO Prolog.

EOF ej-05.txt