Grafos

Grafos y espacios de estados

Ingeniería Informática Ingeniería Técnica en Informática Departamento de Lenguajes y Ciencias de la Computación Universidad de Málaga

Contenido
1. Grafos 2. Espacios de estados

Grafos y espacios de estados

2

Grafos

Grafos
Definición: Un grafo G es un par (N, A) donde N es un conjunto N finito y A es una relación binaria sobre N A⊆ N × N Loselementos de N se llaman nodos, los de A, arcos. Definición: Si la relación A es simétrica: ∀ x, y. (x, y) ∈ A ⇒ (y, x) ∈ A se dice que G es un grafo no dirigido, de lo contrario G es un grafo dirigido Los pares (x,y) y (y,x) componen una arista.
Grafos y espacios de estados 4

Representación de grafos dirigidos (I)
Ejemplo: N = {a,b,c}, A = {(a,b), (b,c), (c,a)}

a c

b

Lasrepresentaciones más comunes son: listas de adyacencia matriz de adyacencia ¿Cuál es la forma más adecuada de representar un grafo en Prolog?

Grafos y espacios de estados

5

Representación de grafos dirigidos (y II)
A es una relación entre objetos (nodos), lo más simple es representarla con un predicado arco/2: arco(a,b). arco(b,c). arco(c,a). El dominio de los nodos se define extensionalmentees_nodo/1: es_nodo(a). es_nodo(b). es_nodo(c). o bien intensionalmente, a partir de arco/2: es_nodo(X):-arco(X,_). es_nodo(X):-arco(_,X).
Grafos y espacios de estados 6

¿Y si hay más de un grafo en mi programa?
Basta añadir un identificador único para cada grafo. Ejemplo: grafos G1 y A-92 % arco(+ident,?nodo,?nodo) arco(g1,a,b). arco(a92,malaga,sevilla). arco(g1,b,c). arco(a92,malaga,granada).arco(g1,c,a). arco(a92,granada,almeria). Este identificador también se emplea en la definición de nodos: es_nodo(Id,X):-arco(Id,X,_). es_nodo(Id,X):-arco(Id,_,X).
Grafos y espacios de estados 7

Representación de grafos no dirigidos (I)
Una posibilidad es definir dos hechos por cada arista: arista(a,b). arista(b,a). arista(b,c). arista(c,b). arista(c,a). arista(a,c). ¿Puedes pensar una soluciónmejor?...

a c

b

Grafos y espacios de estados

8

Cierre o clausura de una relación binaria
Definición: Dada una relación A, llamamos cierre o clausura de A a una relación A’ tal que A ⊆ A’ A’ se obtiene añadiendo tuplas a A A A A’

Cerramos A añadiendo el número mínimo de tuplas tal que A’ satisfaga cierta propiedad (reflexiva, simétrica,…) Ejemplo: cierre simétrico A’ = A ∪ {(y,x) / (x,y) ∈ A }
Grafos y espacios de estados

9

Representación de grafos no dirigidos (y II)
La relación arista/2 es el cierre simétrico de arco/2: arco(a,b). arco(b,c). arco(c,a). A’ = A ∪ { (y,x) / (x,y) ∈ A } arista(X,Y) :- arco(X,Y). arista(Y,X) :- arco(X,Y). La representación de los nodos es la misma que en los grafos dirigidos.
Grafos y espacios de estados 10

a c

bConectividad en grafos (I)
conectados(?X,?Y) – hay un camino que une X e Y conectados(X,X) :es_nodo(X). conectados(X,Y) :arco(X,Z), conectados(Z,Y). La relación conectados/2 es el cierre reflexivo y transitivo de la relación arco/2. Si el grafo es no dirigido, basta reemplazar arco/2 por arista/2. Problema: ¿Y si el grafo es cíclico?
Grafos y espacios de estados 11

Conectividad en grafos (II) a c b:- conectados(a,b). :- arco(a,Z1),conectados(Z1,b). Z1/b :- conectados(b,b). :- es_nodo(b). :- arco(b,Z2),conectados(Z2,b). Z2/c :- conectados(c,b). :- arco(c,Z3),conectados(Z3,b). Z3/a
Grafos y espacios de estados

12

Conectividad en grafos (y III)
Podemos añadir una lista con los nodos visitados: conectados(X,Y) :conectados(X,Y,[X]). % conectados(?X,?Y,+Visitados) conectados(X,X,_):es_nodo(X). conectados(X,Y,Visitados) :arco(X,Z), no_esta(Z,Visitados), conectados(Z,Y,[Z|Visitados]). Visitados está siempre instanciada (modo +) ¿Cómo modificarlo para obtener el camino de X a Y?
Grafos y espacios de estados 13

Caminos en un grafo (I)
camino(?X,?Y,?Cs) – Cs es un camino de X a Y camino(X,Y,Cs) :camino(X,Y,[X],Cs). % camino(?X,?Y,+Visitados,?Camino) camino(X,X,Visitados,Cs)...