Grafos

Grafos 2

Clasificación de Grafos

Los grafos se utilizan en aplicaciones muy diversas (redes de comunicaciones, redes de transporte, circuitos, planificación de tareas) cada una de las cuales utiliza una noción distinta de grafo.Los grafos de pueden clasificar atendiendo

Al número de arcos que puedan existir entre dos nodos: Grafos múltiples (vuelos entre aeropuertos) Grafos simples (líneas de ferrocarril)

A la orientación de los arcos:Grafos orientados (vuelos entre aeropuertos)Grafos no orientados (red de carreteras, líneas de teléfono)

A la existencia de funciones definidas sobre los arcos o los nodos:Grafos no valorados Grafos valorados (red de carreteras con kms, vuelos con duración)

Grafos 3

Nociones de Grafo Orientado

La noción más general corresponde a un grafo orientado con posibilidad de múltiples arcos entre dos nodos (grafo múltiple orientado):

G = (N,A,o,d)N conjunto de nodosA conjunto de arcoso,d : A -> N aplicaciones origen y destino

Cuando sólo se admite la posibilidad de un arco, a lo más, entrecada dos nodos (grafo simple orientado), cada arco a puede identificarse con el par de nodos (o(a),d(a)) y los grafos con las relaciones binarias entre nodos:

G = (N, A) , con A ⊆ N×N.

Grafos 4

Grafos orientados

Los grafos orientados se pueden generar de muchas formas:

a partir de un conjunto inicial de nodos aislados, estableciendoarcos entre dichos nodos;a partir de un conjunto inicial de nodos aislados, estableciendoarcos que pueden involucrar nuevos nodos;a partir de un conjunto inicial de nodos, añadiendo conjuntos desucesores a los nodos establecidos; a partir de un conjunto vacío de arcos añadiendo arcos (y sus correspondientes nodos)....

Grafos 5

Grafos múltiples orientados

Los grafos múltiples orientados se pueden representar también como pares

G = (N,{(a,o(a),d(a))|a ∈ A})donde las aplicaciones o y d quedan definidas de forma implícita.

Estas representaciones se pueden generar, de forma incremental, a partir de un conjunto inicial de nodos aislados añadiendo tripletas (a,n1,n2) en las que n1 y n2 pueden ser nodos del conjunto inicial o pueden ser nodos nuevos.

Grafos 6

Grafos Múltiples Orientados (I)

(fmod GRAFOmOR [N :: TRIV; A :: TRIV] isprotecting CONJUNTO[N] .protecting CONJUNTO[A] .protecting LISTA[A] .sorts GMO[N,A] Elt? .subsort Cj[N] < GMO[N,A] .subsort Elt.N < Elt? .op _[_:_->_] : GMO[N,A] Elt.A Elt.N Elt.N -> GMO[N,A] [ctor] .

var G: GMO[N, A] . vars N1 N2 N3 N4: Elt.N . vars A1 A2: Elt.A .eq G[A1:N1->N2][A2:N3->N4] = if A1 == A2 then G[A2:N3->N4]

else G[A2:N3->N4][A1:N1->N2] fi .

Grafos 7

Grafos Múltiples Orientados (II)op arcos : GMO[N,A] -> Cj[A] .

op borrarArc : Elt.A GMO[N,A] -> GMO[N,A] .

op nodos : GMO[N,A] -> Cj[N] .

op sucs : Elt.N GMO[N,A] -> Cj[N] .ops origen destino : Elt.A GMO[N,A] -> Elt?.N .op esCamino? : ListaNv[A] GMO[N,A] -> Bool .ops origen destino : ListaNv[A] GMO[N,A] -> Elt? .

var C: Cj[N] . var L : ListaNv[A] .

eq arcos(C) = {} .eq arcos(G[A1:N1->N2]) = {A1,arcos(G)} .eq borrarArc(A2,C) = C.eq borrarArc(A2,G[A1:N1->N2]) =

if A2 == A1 then borrarArc(A2,G) else (borrarArc(A2,G))[A1:N1->N2] fi .

Grafos 8

Grafos Múltiples Orientados (III)

eq nodos(C) = C .eq nodos(G[A1:N1->N2]) = {N2,{N1,nodos(borrarArc(A1,G))}} .eq sucs(N3,C) = {} .eq sucs(N3,G[A1:N1->N2]) =

if N3 == N1 then {N2,sucs(N3,borrarArc(A1,G))} else sucs(N3,borrarArc(A1,G)) fi .

eq origen(A2,G[A1:N1->N2]) = if A2 == A1 then N1 else origen(A2, G) fi.

eq destino(A2,G[A1:N1->N2]) = if A2 == A1 then N2 else destino(A2,G) fi .

Grafos 9

Grafos Múltiples Orientados (IV)

eq esCamino?(A1:nil,G) = pertenece?(A1,arcos(G)) .eq esCamino?(A1:L,G) =

if pertenece?(A1,arcos(G)) then (destino(A1) == origen(cabeza(L))) and esCamino?(L,G) else false fi .

eq origen(L,G) = origen(cabeza(L),G) .

eq destino(A1:nil,G) = destino(A1,G) .eq destino(A1:L,G) = destino(L,G) .

endfm)

Grafos 10

Ejercicios

Especificad, para grafos múltiples orientados, las operaciones siguientes:

preds : Elt.N GMO[N] -> Cj[N]existeArco? : Elt.N Elt.N GMO[N] -> BoolborrarNodo : Elt.N GMO[N] -> GMO[N]

que determinen, para un grafo dado, el conjunto de predecesores de un nodo, si existe un arco entre dos nodos y el grafo resultante de eliminar un cierto nodo (y los arcos relacionados), respectivamente.Volved a enunciar la especificación de grafo múltiple orientado con la restricción de que sólo se puedan añadir arcos con los extremos dentro del conjunto inicial de nodos.

Grafos 11

Grafos simples orientados

Los grafos simples orientados se pueden representar como pares G = (N,A)

donde el conjunto de arcos A es un conjunto de pares de nodos.

Estas representaciones se pueden generar también, de forma incremental, a partir de un conjunto inicial de nodos aislados, añadiendo pares (n1, n2), siendo n1 y n2 nodos del conjunto inicial o nodos nuevos, incrementando así el conjunto de arcos y posiblemente el conjunto de nodos.

Grafos 12

Grafos simples orientados (I)

(fmod GRAFOsOR [N :: TRIV] isprotecting CONJUNTO[N] .protecting LISTA[N] .sort GSO[N] .subsort Cj[N] < GSO[N] .op _[_ -> _] : GSO[N] Elt.N Elt.N -> GSO[N] [ctor] .op borrarArc : Elt.N Elt.N GSO[N] -> GSO[N] .op nodos : GSO[N] -> Cj[N] .op sucs : Elt.N GSO[N] -> Cj[N] .op esArco? : Elt.N Elt.N GSO[N] -> Bool .op esCamino? : ListaNv[N] GSO[N] -> Bool .vars N1 N2 N3 N4 : Elt.N . var G : GSO[N,A] .var C : Cj[N] . var L : ListaNv[N] .

Grafos 13

Grafos simples orientados (II)

eq G[N1->N2][N3->N4] = if (N1 == N3) and (N2 == N4) then G[N1->N2]else G[N3->N4][N1->N2] fi .

eq nodos(C) = C .eq nodos(G[N1->N2]) = {N1, {N2,nodos(G)}} .eq esArco?(N1,N2,C) = false .eq esArco?(N1,N2,G[N3->N4]) =

if (N1 == N3) and (N2 == N4) then trueelse esArco?(N1,N2,G) fi .

eq sucs(N3,C) = {} .eq sucs(N3,G[N1->N2]) =

if N3 == N1 then {N2,sucs(N3,G)} else sucs(N3,G) fi .

Grafos 14

Grafos simples orientados (III)

eq borrarArc(N3,N4,C) = C .eq borrarArc(N3,N4,G[N1->N2]) =

if (N3 == N1) and (N4 == N2) then borraArc(N3,N4,G)else (borraArc(N3,N4,G))[N1->N2] fi .

eq esCamino?(L,C) = false .eq esCamino?(N1:nil,G) = false .eq esCamino?(N1:L,G) =

if cola(L) == nil then esArco?(N1,cabeza(L),G)else esArco?(N1,cabeza(L),G) and esCamino?(L,G) fi .

endfm)

Grafos 15

Recorridos sobre Grafos (I)

La mayoría de las operaciones importantes que se realizan sobre un grafo (cálculo de caminos, caminos mínimos, componentes conexas, etc.) requieren de un recorrido sobre el grafo.

Los grafos se pueden recorrer en profundidad y en amplitud. El primero se utiliza para identificar propiedades estructurales y el segundo para propiedades en las que las características estructurales no son relevantes.

A diferencia de los árboles, cuando se elimina un nodo en un grafo el número de componentes conexas que resulta puede ser menor que el número de sucesores del nodo. Algún sucesor, o incluso elpropio nodo, puede ser alcanzable desde otro sucesor.

Grafos 16

Recorridos sobre Grafos (II)

En consecuencia, para recorrer un grafo hay que utilizar:algún procedimiento para seleccionar nodos y algún procedimiento para marcar los nodos visitados de manera que no se vuelva a ellos.

Se necesita una ordenación de los nodos para que se pueda construir una lista a partir del conjunto de nodos (lista de candidatos) que marque un orden de visita.

De la lista de candidatos se saca el primer nodo y, si no ha sido visitado, pasa al final del recorrido y la lista de sus sucesores se incorpora a la lista de candidatos al comienzo (recorrido en profundidad) o al final (recorrido en amplitud); en cambio, si ha sido visitado, se quita y se considera el candidato siguiente.

Grafos 17

Recorridos sobre Grafos (III)

(fmod GSORECORRIDOS [N :: TOSET] isprotecting GRAFOsOR[Ord][N] .protecting CONJUNTOORD[N] .op listaProf : GSO[Ord][N] -> Lista[Ord][N] .op ilistaProf: GSO[Ord][N] Lista[Ord][N] Lista[Ord][N] ->

Lista[Ord][N] .op listaAmp : GSO[Ord][N] -> Lista[Ord][N] .op ilistaAmp: GSO[Ord][N] Lista[Ord][N] Lista[Ord][N] ->

Lista[Ord][N] .op elimLista : Lista[Ord][N] Cj[Ord][N] -> Cj[Ord][N] .

var N1 : Elt.N . vars L1 L2 : Lista[Ord][N] .var G : GSO[Ord][N] . var C : Cj[Ord][N] .

Grafos 18

Recorridos sobre Grafos (IV)

eq listaProf(G) = ilistaProf(G,listado(nodos(G)),nil) .eq ilistaProf(G,nil,L1) = L1 . eq ilistaProf(G,N1:L1,L2) =

if esta(N1,L2) then ilistaProf(G,L1,L2) else ilistaProf(G,listado(sucs(N1,G))++L1,L2++(N1:nil)) fi .

eq listaAmp(G) = ilistaAmp(G,cabeza(listado(nodos(G))),nil) .eq ilistaAmp(G,nil,L1) =

if longitud(L1)==card(nodos(G)) then L1else ilistaAmp(G,cabeza(listado(elimLista(L1,nodos(G)))),L1) fi .

eq ilistaAmp(G,N1:L1,L2) = if esta(N1,L2) then ilistaAmp(G,L1,L2) else ilistaAmp(G,L1++listado(sucs(N1,G)),L2++(N1:nil)) fi .

eq elimLista(nil,C) = C .eq elimLista(N1:L1,C) = elimLista(L1,eliminar(N1,C)) .

endfm)

Grafos 19

Ejercicios

Especificar cada una de las operaciones siguientes sobre grafos simples orientados con recorridos:

accesibles : Elt.N GSO[N] -> Lista[Ord][N] .hayCamino? : Elt.N Elt.N GSO[N] -> Bool .equivalentes? : Elt.N Elt.N GSO[N] -> Bool .aciclico? : GSO[N] -> Bool .fConexo : GSO[N] -> Bool .

que determinen, respectivamente, el conjunto de nodos que se pueden alcanzar desde un nodo dado, si hay un camino desde el primer nodo al segundo, si hay caminos para pasar de cada uno delos nodos al otro, si no existen ciclos en el grafo o si el grafo es fuertemente conexo (hay un nodo equivalente con todos los demás)

Grafos 20

Grafos como conjuntos de arcos

Los grafos simples orientados G = (N, A), cuando no se contempla la posibilidad de nodos aislados, se pueden considerar como conjuntos de arcos, es decir, como conjuntos de pares de nodos.

Estas representaciones se pueden generar, de forma parecida a las funciones parciales, a partir de un conjunto vacío de arcos, agregando arcos uno a uno.

Grafos 21

Grafos: conjuntos de arcos (I)

fmod GRAFOor [N :: TRIV] isprotecting CONJUNTO[N] . protecting LISTA[N] .sort GSO[N] .op gfoV : -> GSO[N] [ctor] .op _ (_->_) : GSO[N] Elt.N Elt.N -> GSO[N] [ctor] .op nodos : GSO[N] -> Cj[N] .op sucs : Elt.N GSO[N] -> Cj[N] .op borrarArc : Elt.N Elt.N GSO[N] -> GSO[N] .op esArco? : Elt.N Elt.N GSO[N] -> Bool .op esCamino? : ListaNv[N] GSO[N] -> Bool .

vars N1 N2 N3 N4 : Elt.N . var G : GSO[N] .var L : ListaNv[N] .

eq G(N1->N2)(N3->N4) = if (N1==N3 and N2==N4) then G(N1->N2) else G(N3->N4)(N1->N2) fi .

Grafos 22

Grafos: conjuntos de arcos (II)eq nodos(gfoV) = {} .eq nodos(G(N1->N2)) = {N1,N2,nodos(G)} .eq sucs(N3,gfoV) = {} .eq sucs(N3,G(N1->N2)) = if N3 == N1 then {N2,sucs(N3,G)}

else sucs(N3,G) fi .eq borrarArc((N3->N4),gfoV) = gfoV .eq borrarArc((N3->N4),G(N1->N2)) =

if N3 == N1 and N4 == N2 then borrarArc((N3->N4),G) else (borrarArc((N3->N4),G))(N1->N2) fi .

eq esArco?(N3,N4,gfoV) = false .eq esArco?(N3,N4,G(N1->N2)) = if N3 == N1 and N4 == N2 then true

else esArco?(N3,N4,G) fi . eq esCamino?(N1:nil,G) = false .eq esCamino?(N1:L,G) = if cola(L) == nil then esArco?(N1,cabeza(L),G)

else esArco?(N1,cabeza(L),G)and esCamino?(L,G) fi .

endfm)

Grafos 23

Grafos no Orientados

Los grafos no orientados se caracterizan porque en ellos, el orden de los extremos de los arcos no tiene ninguna relevancia.En el caso de grafos múltiples serían grafos con una función extremo definida sobre los arcos (en lugar de las funciones o y d), que asigna un conjunto de dos nodos a cada arco.En el caso de los grafos simples se pueden identificar con aquellos correspondientes a relaciones simétricas (por cada arco a->b debe haber otro b->a). En cualquier caso siempre se puede enunciar una especificación adecuada a grafos no orientados con nomenclatura propia donde cada eje a<->b es equivalente a b<->a.

Grafos 24

Grafos no Orientados (I)

(fmod GRAFOsNOr [N :: TOSET] isprotecting CONJUNTOORD[N] .protecting LISTA[Ord][N] .sorts GsNo[N] GsNo?[N] .subsorts Cj[Ord][N] < GsNo[N] < GsNo?[N] .op conectar : Elt.N Elt.N GsNo[N] -> GsNo?[N] [ctor].-- solo nodos del conjunto inicial op nodos : GsNo[N] -> Cj[Ord][N] .op adyacs : Elt.N GsNo[N] -> Cj[Ord][N] .op desconectar : Elt.N Elt.N GsNo[N] -> GsNo[N] .op borrarNodo : Elt.N GsNo[N] -> GsNo[N] .op esArista? : Elt.N Elt.N GsNo[N] -> Bool .op esCamino? : ListaNv[Ord][N] GsNo[N] -> Bool .op listaProf : GsNo[N] -> Lista[Ord][N] .op ilistaProf : GsNo[N] Lista[Ord][N] Lista[Ord][N] ->

Lista[Ord][N] .

Grafos 25

Grafos no Orientados (II)

vars N1 N2 N3 N4 : Elt.N . var G : GsNo[N] .

var C : Cj[Ord][N] . cmb conectar(N1,N2,G) : GsNo[N]

if esta?(N1,nodos(G)) and esta?(N2,nodos(G)) .eq conectar(N3,N4,conectar(N1,N2,G)) =

if (N3==N1 and N4==N2) or (N3==N2 and N4==N1) then conectar(N1,N2,G)else conectar(N1,N2,conectar(N3,N4,G)) fi.

eq nodos(C) = C .ceq nodos(conectar(N1,N2,G)) = nodos(G)

if esta?(N1,nodos(G)) and esta?(N2,nodos(G)) ....endfm)

Grafos 26

Ejercicios (I)

Completar la especificación anteriorAñadir a la especificación anterior las operaciones siguientes:

accesibles : Elt.N GsNo[N] -> CjOr[N] .hayCamino? : Elt.N Elt.N GsNo[N] -> Bool .aciclico? : GsNo[N] -> Bool .conexo? : GsNo[N] -> Bool .

que determinen, respectivamente, el conjunto de nodos que se pueden alcanzar desde un nodo dado, si hay un camino entre el primer nodo y el segundo, si no existen ciclos en el grafo o si el grafo es conexo (todos los nodos está conectados)

Grafos 27

Ejercicios (II)

Sobre la especificación dada para grafos simples no orientados, especificad las operaciones siguientes:

caminoP : Elt.N Elt.N GsNo[N] -> Lista[Ord][N] .unionG : GsNo[N] GsNo[N] -> GsNo[N] .compConexa : Elt:N GsNo[N] -> GsNo[N] .

que calculen, respectivamente, un camino desde primer nodo al segundo siguiendo un recorrido en profundidad, la unión de dos grafos y el subgrafo conexo maximal que contiene a un nodo.

Grafos 28

Valoraciones sobre grafos