Ir al contenido principal

TAD de los grafos - Nodos conectados en un grafo

El tipo abstracto de datos de los grafos

Usando el tipo abstrado de datos de los grafos, definir la función

   conectados :: Grafo Int Int -> Int -> Int -> Bool

tal que conectados g v1 v2 se verifica si los vértices v1 y v2 están conectados en el grafo g. Por ejemplo, si grafo1 es el grafo definido por

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50),
                                (2,4),(2,6),(4,6),(4,4),(6,4)]

entonces,

   conectados grafo1 1 3  ==  True
   conectados grafo1 1 4  ==  False
   conectados grafo1 6 2  ==  False
   conectados grafo1 3 1  ==  True

Leer más…

TAD de los grafos - Nodos aislados de un grafo

El tipo abstracto de datos de los grafos

Dado un grafo dirigido G, diremos que un nodo está aislado si o bien de dicho nodo no sale ninguna arista o bien no llega al nodo ninguna arista. Por ejemplo, en el siguiente grafo

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),
                                (5,4),(6,2),(6,5)]

podemos ver que del nodo 1 salen 3 aristas pero no llega ninguna, por lo que lo consideramos aislado. Así mismo, a los nodos 2 y 4 llegan aristas pero no sale ninguna, por tanto también estarán aislados.

Usando el tipo abstrado de datos de los grafos, definir la función

   aislados :: (Ix v, Num p) => Grafo v p -> [v]

tal que aislados g es la lista de nodos aislados del grafo g. Por ejemplo,

   aislados grafo1 == [1,2,4]

Leer más…

TAD de los grafos - Coloreado correcto de un mapa

El tipo abstracto de datos de los grafos

Un mapa se puede representar mediante un grafo donde los vértices son las regiones del mapa y hay una arista entre dos vértices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente

   +----------+----------+
   |    1     |     2    |
   +----+-----+-----+----+
   |    |           |    |
   | 3  |     4     | 5  |
   |    |           |    |
   +----+-----+-----+----+
   |    6     |     7    |
   +----------+----------+

se pueden representar por

   mapa :: Grafo Int Int
   mapa = creaGrafo' ND (1,7)
                     [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),
                      (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)]

Para colorear el mapa se dispone de 4 colores definidos por

   data Color = A | B | C | D
     deriving (Eq, Show)

Usando el tipo abstrado de datos de los grafos, definir la función

   correcta :: [(Int,Color)] -> Grafo Int Int -> Bool

tal que correcta ncs m se verifica si ncs es una coloración del mapa m tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,

   correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa == True
   correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa == False

Leer más…

TAD de los grafos - Grafos conexos

El tipo abstracto de datos de los grafos

Un grafo no dirigido G se dice conexo, si para cualquier par de vértices u y v en G, existe al menos una trayectoria (una sucesión de vértices adyacentes) de u a v.

Usando el tipo abstrado de datos de los grafos, definir la función

   conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool

tal que conexo g se verifica si el grafo g es conexo. Por ejemplo,

   conexo (creaGrafo' ND (1,3) [(1,2),(3,2)])        ==  True
   conexo (creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)])  ==  True
   conexo (creaGrafo' ND (1,4) [(1,2),(3,4)])        ==  False

Leer más…

TAD de los grafos - Recorrido en anchura

El tipo abstracto de datos de los grafos

Usando el tipo abstrado de datos de los grafos, definir la función

   recorridoEnAnchura :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]

tal que recorridoEnAnchura i g es el recorrido en anchura del grafo g desde el vértice i. Por ejemplo, en el grafo

   +---> 2 <---+
   |           |
   |           |
   1 --> 3 --> 6 --> 5
   |                 |
   |                 |
   +---> 4 <---------+

definido por

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]

entonces

   recorridoEnAnchura 1 grafo1  ==  [1,2,3,4,6,5]

Leer más…

TAD de los grafos - Recorrido en profundidad

El tipo abstracto de datos de los grafos

Usando el tipo abstrado de datos de los grafos, definir la función

   recorridoEnProfundidad :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]

tal que recorridoEnProfundidad i g es el recorrido en profundidad del grafo g desde el vértice i. Por ejemplo, en el grafo

   +---> 2 <---+
   |           |
   |           |
   1 --> 3 --> 6 --> 5
   |                 |
   |                 |
   +---> 4 <---------+

definido por

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]

entonces

   recorridoEnProfundidad 1 grafo1  ==  [1,2,3,6,5,4]

Leer más…

TAD de los grafos - Anchura de un grafo

El tipo abstracto de datos de los grafos

En un grafo, la anchura de un nodo es el máximo de los absolutos de la diferencia entre el valor del nodo y los de sus adyacentes; y la anchura del grafo es la máxima anchura de sus nodos. Por ejemplo, en el grafo

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),
                                (2,4),(2,5),
                                (3,4),(3,5),
                                (4,5)]

su anchura es 4 y el nodo de máxima anchura es el 5.

Usando el tipo abstrado de datos de los grafos, definir la función

   anchura :: Grafo Int Int -> Int

tal que (anchuraG g) es la anchura del grafo g. Por ejemplo,

   anchura grafo1  ==  4

Comprobar experimentalmente que la anchura del grafo ciclo de orden n es n-1.

Leer más…

TAD de los grafos - Recorridos en un grafo completo

El tipo abstracto de datos de los grafos

Definir la función

   recorridos :: [a] -> [[a]]

tal que recorridos xs es la lista de todos los posibles por el grafo cuyo conjunto de vértices es xs y cada vértice se encuentra conectado con todos los otros y los recorridos pasan por todos los vértices una vez y terminan en el vértice inicial. Por ejemplo,

   λ> recorridos [2,5,3]
   [[2,5,3,2],[5,2,3,5],[3,5,2,3],[5,3,2,5],[3,2,5,3],[2,3,5,2]]

Leer más…

TAD de los grafos - Grafos k-regulares

El tipo abstracto de datos de los grafos

Un grafo k-regular es un grafo con todos sus vértices son de grado k.

Usando el tipo abstrado de datos de los grafos, definir la función

   regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int

tal que (regularidad g) es la regularidad de g. Por ejemplo,

   regularidad (creaGrafo' ND (1,2) [(1,2),(2,3)]) == Just 1
   regularidad (creaGrafo' D (1,2) [(1,2),(2,3)])  == Nothing
   regularidad (completo 4)                        == Just 3
   regularidad (completo 5)                        == Just 4
   regularidad (grafoCiclo 4)                      == Just 2
   regularidad (grafoCiclo 5)                      == Just 2

Comprobar que el grafo completo de orden n es (n-1)-regular (para n de 1 a 20) y el grafo ciclo de orden n es 2-regular (para n de 3 a 20).

Leer más…

TAD de los grafos - Grafos regulares

El tipo abstracto de datos de los grafos

Un grafo regular es un grafo en el que todos sus vértices tienen el mismo grado.

Usando el tipo abstrado de datos de los grafos, definir la función

   regular :: (Ix v,Num p) => Grafo v p -> Bool

tal que (regular g) se verifica si el grafo g es regular. Por ejemplo,

   λ> regular (creaGrafo' D (1,3) [(1,2),(2,3),(3,1)])
   True
   λ> regular (creaGrafo' ND (1,3) [(1,2),(2,3)])
   False
   λ> regular (completo 4)
   True

Comprobar que los grafos completos son regulares.

Leer más…