El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal.

Las posiciones de las reinas en el tablero se representan por su columna y su fila.

   type Columna = Int
   type Fila    = Int

Una solución del problema de las n reinas es una lista de posiciones.

type SolNR = [(Columna,Fila)]

Usando el procedimiento de búsqueda en anchura, definir las funciones

   solucionesNR      :: Columna -> [SolNR]
   primeraSolucionNR :: Columna -> SolNR
   nSolucionesNR     :: Columna -> Int

tales que

• solucionesNR n es la lista de las soluciones del problema de las n reinas, por búsqueda de espacio de estados en anchura. Por ejemplo,

     take 3 (solucionesNR 8)
     [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],
      [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],
      [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]

• primeraSolucionNR n es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por anchura. Por ejemplo,

     λ> primeraSolucionNR 8
     [(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)]

• nSolucionesNR n es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,

     nSolucionesNR 8  ==  92

Leer más…

Las características de los problemas de espacios de estados son:

• un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),
• un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,
• un nodo inicial y
• un nodo objetivo que es la solución.

Definir la función

   buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)
                              -> nodo -> [nodo]

tal que buscaAnchura s o e es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e obtenidas mediante búsqueda en anchura.

Leer más…

Las características de los problemas de espacios de estados son:

• un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),
• un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,
• un nodo inicial y
• un nodo objetivo que es la solución.

Definir la función

   buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)
                                  -> nodo -> [nodo]

tal que buscaProfundidad s o e es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e obtenidas mediante búsqueda en profundidad.

Leer más…

Un poliominó es una figura geométrica plana formada conectando dos o más cuadrados por alguno de sus lados. Los cuadrados se conectan lado con lado, pero no se pueden conectar ni por sus vértices, ni juntando solo parte de un lado de un cuadrado con parte de un lado de otro. Si unimos dos cuadrados se obtiene un dominó, si se juntan tres cuadrados se construye un triominó.

Sólo existen dos triominós, el I-triomino (por tener forma de I) y el L-triominó (por su forma de L) como se observa en las siguientes figuras

   X
   X     X
   X     XX

El rompecabeza del triominó consiste en cubrir un tablero cuadrado con 2^n filas y 2^n columnas, en el que se ha eliminado una casilla, con L-triominós de formas que cubran todas las casillas excepto la eliminada y los triominós no se solapen.

La casilla eliminada se representará con -1 y los L-triominós sucesiones de tres números consecutivos en forma de L. Con esta representación una solución del rompecabeza del triominó con 4 filas y la fila eliminada en la posición (4,4) es

   (  3  3  2  2 )
   (  3  1  1  2 )
   (  4  1  5  5 )
   (  4  4  5 -1 )

Definir la función

   triomino :: Int -> Posicion -> Tablero

tal que (triomino n p) es la solución, mediante divide y vencerás, del rompecabeza del triominó en un cuadrado nxn en el que se ha eliminado la casilla de la posición p. Por ejemplo,

   λ> triomino 4 (4,4)
   (  3  3  2  2 )
   (  3  1  1  2 )
   (  4  1  5  5 )
   (  4  4  5 -1 )

   λ> triomino 4 (2,3)
   (  3  3  2  2 )
   (  3  1 -1  2 )
   (  4  1  1  5 )
   (  4  4  5  5 )

   λ> triomino 16 (5,6)
   (  7  7  6  6  6  6  5  5  6  6  5  5  5  5  4  4 )
   (  7  5  5  6  6  4  4  5  6  4  4  5  5  3  3  4 )
   (  8  5  9  9  7  7  4  8  7  4  8  8  6  6  3  7 )
   (  8  8  9  3  3  7  8  8  7  7  8  2  2  6  7  7 )
   (  8  8  7  3  9 -1  8  8  7  7  6  6  2  8  7  7 )
   (  8  6  7  7  9  9  7  8  7  5  5  6  8  8  6  7 )
   (  9  6  6 10 10  7  7 11  8  8  5  9  9  6  6 10 )
   (  9  9 10 10 10 10 11 11  1  8  9  9  9  9 10 10 )
   (  8  8  7  7  7  7  6  1  1  9  8  8  8  8  7  7 )
   (  8  6  6  7  7  5  6  6  9  9  7  8  8  6  6  7 )
   (  9  6 10 10  8  5  5  9 10  7  7 11  9  9  6 10 )
   (  9  9 10  4  8  8  9  9 10 10 11 11  5  9 10 10 )
   (  9  9  8  4  4 10  9  9 10 10  9  5  5 11 10 10 )
   (  9  7  8  8 10 10  8  9 10  8  9  9 11 11  9 10 )
   ( 10  7  7 11 11  8  8 12 11  8  8 12 12  9  9 13 )
   ( 10 10 11 11 11 11 12 12 11 11 12 12 12 12 13 13 )

Leer más…

La técnica divide y vencerás consta de los siguientes pasos:

• Dividir el problema en subproblemas menores.
• Resolver por separado cada uno de los subproblemas:
• si los subproblemas son complejos, usar la misma técnica recursivamente;
• si son simples, resolverlos directamente.
• Combinar todas las soluciones de los subproblemas en una solución simple.

Definir la función

   divideVenceras :: (p -> Bool)
                  -> (p -> s)
                  -> (p -> [p])
                  -> (p -> [s] -> s)
                  -> p
                  -> s

tal que divideVenceras ind resuelve divide combina pbInicial resuelve el problema pbInicial mediante la técnica de divide y vencerás, donde

• ind pb se verifica si el problema pb es indivisible
• resuelve pb es la solución del problema indivisible pb
• divide pb es la lista de subproblemas de pb
• combina pb ss es la combinación de las soluciones ss de los subproblemas del problema pb.
• pbInicial es el problema inicial

Usando la función DivideVenceras, definir las funciones

   ordenaPorMezcla :: Ord a => [a] -> [a]
   ordenaRapida    :: Ord a => [a] -> [a]

tales que

• ordenaPorMezcla xs es la lista obtenida ordenando xs por el procedimiento de ordenación por mezcla. Por ejemplo,

     λ> ordenaPorMezcla [3,1,4,1,5,9,2,8]
     [1,1,2,3,4,5,8,9]

• ordenaRapida xs es la lista obtenida ordenando xs por el procedimiento de ordenación rápida. Por ejemplo,

     λ> ordenaRapida [3,1,4,1,5,9,2,8]
     [1,1,2,3,4,5,8,9]

Leer más…

El algoritmo de Prim calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Prim funciona de la siguiente manera:

• Inicializar un árbol con un único vértice, elegido arbitrariamente, del grafo.
• Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
• Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)

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

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

tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

   g1, g2, g3, g4 :: Grafo Int Int
   g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                            (2,4,55),(2,5,32),
                            (3,4,61),(3,5,44),
                            (4,5,93)]
   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),
                            (2,4,12),(2,5,32),
                            (3,4,14),(3,5,44),
                            (4,5,93)]
   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,7),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]
   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,1),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]

entonces

   prim g1  == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
   prim g2  == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]
   prim g3  == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]

Leer más…

El algoritmo de Kruskal calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Kruskal funciona de la siguiente manera:

• se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado
• se crea un conjunto C que contenga a todas las aristas del grafo
• mientras C es no vacío,
• eliminar una arista de peso mínimo de C
• si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
• en caso contrario, se desecha la arista

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

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

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

tal que kruskal g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Kruskal. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

   g1, g2, g3, g4 :: Grafo Int Int
   g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                            (2,4,55),(2,5,32),
                            (3,4,61),(3,5,44),
                            (4,5,93)]
   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),
                            (2,4,12),(2,5,32),
                            (3,4,14),(3,5,44),
                            (4,5,93)]
   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,7),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]
   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,1),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]

entonces

   kruskal g1  ==  [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
   kruskal g2  ==  [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]
   kruskal g3  ==  [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]
   kruskal g4  ==  [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]

Leer más…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

En la teoría de grafos, se conoce como "Lema del apretón de manos" la siguiente propiedad: la suma de los grados de los vértices de g es el doble del número de aristas de g.

Comprobar con QuickCheck que para cualquier grafo g, se verifica dicha propiedad.

Leer más…

El grado de un vértice v de un grafo dirigido g, es el número aristas de g que contiene a v. Si g es no dirigido, el grado de un vértice v es el número de aristas incidentes en v, teniendo en cuenta que los lazos se cuentan dos veces.

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

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

tal que grado g v es el grado del vértice v en el grafo g. Por ejemplo,

   g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]
   g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]
   g3 = creaGrafo' D  (1,3) [(1,2),(2,2),(3,1),(3,2)]
   g4 = creaGrafo' D  (1,1) [(1,1)]
   g5 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]
   g6 = creaGrafo' D  (1,3) [(1,2),(1,3),(2,3),(3,3)]
   grado g1 5 ==  4
   grado g2 5 ==  3
   grado g2 1 ==  3
   grado g3 2 ==  4
   grado g3 1 ==  2
   grado g3 3 ==  2
   grado g4 1 ==  2
   grado g6 3 ==  4
   grado g6 3 ==  4

Comprobar con QuickCheck que en todo grafo, el número de nodos de grado impar es par.

Leer más…

Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbutrary.

Usando el generador, con QuickCheck que para cualquier grafo g, las sumas de los grados positivos y la de los grados negativos de los vértices de g son iguales.

Leer más…

El grado positivo de un vértice v de un grafo g es el número de vértices de g adyacentes con v y su grado negativo es el número de vértices de g incidentes con v.

Usando el tipo abstrado de datos de los grafos, definir las funciones

   gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int
   gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int

tales que + gradoPos g v es el grado positivo del vértice v en el grafo g. Por ejemplo,

     λ> g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]
     λ> g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]
     λ> gradoPos g1 5
     4
     λ> gradoPos g2 5
     0
     λ> gradoPos g2 1
     3

• gradoNeg g v es el grado negativo del vértice v en el grafo g. Por ejemplo,

     λ> gradoNeg g1 5
     4
     λ> gradoNeg g2 5
     3
     λ> gradoNeg g2 1
     0

Leer más…

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

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

tal que nAristas g es el número de aristas del grafo g. Si g es no dirigido, las aristas de v1 a v2 y de v2 a v1 sólo se cuentan una vez. Por ejemplo,

   λ> g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]
   λ> g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]
   λ> g3 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]
   λ> g4 = creaGrafo' ND (1,4) [(1,1),(1,2),(3,3)]
   λ> nAristas g1
   8
   λ> nAristas g2
   7
   λ> nAristas g3
   4
   λ> nAristas g4
   3
   λ> nAristas (completo 4)
   6
   λ> nAristas (completo 5)
   10

Definir la función

   prop_nAristasCompleto :: Int -> Bool

tal que prop_nAristasCompleto n se verifica si el número de aristas del grafo completo de orden n es n*(n-1)/2 y, usando la función, comprobar que la propiedad se cumple para n de 1 a 20.

Leer más…

Usando el tipo abstrado de datos de los grafos, definir las funciones

   lazos  :: (Ix v,Num p) => Grafo v p -> [(v,v)]
   nLazos :: (Ix v,Num p) => Grafo v p -> Int

tales que

• lazos g es el conjunto de los lazos (es decir, aristas cuyos extremos son iguales) del grafo g. Por ejemplo,

     λ> ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)]
     λ> ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)]
     λ> lazos ej1
     [(1,1),(3,3)]
     λ> lazos ej2
     []

• nLazos g es el número de lazos del grafo g. Por ejemplo,

     λ> nLazos ej1
     2
     λ> nLazos ej2
     0

Leer más…

En un un grafo g, los contiguos de un vértice v es el conjuntos de vértices x de g tales que x es adyacente o incidente con v.

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

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

tal que contiguos g v es el conjunto de los vértices de g contiguos con el vértice v. Por ejemplo,

   λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> contiguos g1 1
   [2,3]
   λ> contiguos g1 2
   [2,1,3]
   λ> contiguos g1 3
   [1,2]
   λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> contiguos g2 1
   [2,3]
   λ> contiguos g2 2
   [1,2,3]
   λ> contiguos g2 3
   [1,2]

Leer más…

En un un grafo g, los incidentes de un vértice v es el conjuntos de vértices x de g para los que hay un arco (o una arista) de x a v; es decir, que v es adyacente a x.

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

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

tal que incidentes g v es la lista de los vértices incidentes en el vértice v. Por ejemplo,

   λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> incidentes g1 1
   [3]
   λ> incidentes g1 2
   [1,2,3]
   λ> incidentes g1 3
   []
   λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> incidentes g2 1
   [2,3]
   λ> incidentes g2 2
   [1,2,3]
   λ> incidentes g2 3
   [1,2]

Leer más…

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

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

tal que nVertices g es el número de vértices del grafo g. Por ejemplo,

   nVertices (creaGrafo' D (1,5) [(1,2),(3,1)])   ==  5
   nVertices (creaGrafo' ND (2,4) [(1,2),(3,1)])  ==  3

Leer más…

El ciclo de orden n, C(n), es un grafo no dirigido cuyo conjunto de vértices es {1,...,n} y las aristas son

   (1,2), (2,3), ..., (n-1,n), (n,1)

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

   grafoCiclo :: Int -> Grafo Int Int

tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,

   λ> grafoCiclo 3
   G ND ([1,2,3],[(1,2),(1,3),(2,3)])

Leer más…

El grafo completo de orden n, K(n), es un grafo no dirigido cuyos conjunto de vértices es {1,..n} y tiene una arista entre cada par de vértices distintos.

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

   completo :: Int -> Grafo Int Int

tal que completo n es el grafo completo de orden n. Por ejemplo,

   λ> completo 4
   G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])

Leer más…

1. El tipo abstracto de datos de los grafos

Un grafo es una estructura que consta de un conjunto de vértices y un conjunto de aristas que conectan los vértices entre sí. Cada vértice representa una entidad o un elemento, y cada arista representa una relación o conexión entre dos vértices.

Por ejemplo,

         12
    1 -------- 2
    | \78     /|
    |  \   32/ |
    |   \   /  |
  34|     5    |55
    |   /   \  |
    |  /44   \ |
    | /     93\|
    3 -------- 4
         61

representa un grafo no dirigido, lo que significa que las aristas tienen una dirección específica. Cada arista tiene un peso asociado, que puede representar una medida o una valoración de la relación entre los vértices que conecta.

El grafo consta de cinco vértices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los vértices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexión entre el vértice 1 y el vértice 2 con un peso de 12.

En el grafo representado, se pueden observar las conexiones entre los vértices de la siguiente manera:

• El vértice 1 está conectado con el vértice 2 (peso 12), el vértice 3 (peso 34) y el vértice 5 (peso 78).
• El vértice 2 está conectado con el vértice 4 (peso 55) y el vértice 5 (peso 32).
• El vértice 3 está conectado con el vértice 4 (peso 61) y el vértice 5 (peso 44).
• El vértice 4 está conectado con el vértice 5 (peso 93).

Las operaciones del tipo abstracto de datos (TAD) de los grafos son

   creaGrafo  :: (Ix v, Num p, Ord v, Ord p) =>
                  Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
   creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
                  Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
   dirigido   :: (Ix v,Num p) => (Grafo v p) -> Bool
   adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
   nodos      :: (Ix v,Num p) => (Grafo v p) -> [v]
   aristas    :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
   aristaEn   :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
   peso       :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p

tales que + creaGrafo o cs as es un grafo (dirigido o no, según el de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso). + creaGrafo' es la versión de creaGrafo para los grafos sin pesos. + dirigido g se verifica si g es dirigido. + nodos g es la lista de todos los nodos del grafo g. + aristas g es la lista de las aristas del grafo g. + adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g. + aristaEn g a se verifica si a es una arista del grafo g. + peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.

Usando el TAD de los grafos, el grafo anterior se puede definir por

   creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                       (2,4,55),(2,5,32),
                       (3,4,61),(3,5,44),
                       (4,5,93)]

con los siguientes argumentos:

• ND: Es un parámetro de tipo Orientacion que indica si el es dirigido o no. En este caso, se utiliza ND, lo que significa "no dirigido". Por lo tanto, el grafo creado será no dirigido, lo que implica que las aristas no tienen una dirección específica.
• (1,5): Es el par de cotas que define los vértices del grafo. En este caso, el grafo tiene vértices numerados desde 1 hasta 5.
• [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),(3,5,44),(4,5,93)]: Es una lista de aristas, donde cada arista está representada por un trío de valores. Cada trío contiene los dos vértices que están conectados por la arista y el peso de dicha arista.

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes: + mediante lista de adyacencia, + mediante vector de adyacencia y + mediante matriz de adyacencia.

Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

Leer más…

Utilizando el tipo abstracto de datos de los polinomios definir la función

   factorizacion :: Polinomio Int -> [Polinomio Int]

tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. Por ejemplo,

   λ> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol1
   x^5 + 5*x^2 + 4*x
   λ> factorizacion ejPol1
   [1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4]
   λ> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
   λ> ejPol2
   x^3 + 2*x^2 + -1*x + -2
   λ> factorizacion ejPol2
   [1*x + -1,1*x + 1,1*x + 2,1]

Leer más…

Utilizando el tipo abstracto de datos de los polinomios definir la función

    raicesRuffini :: Polinomio Int -> [Int]

tal que raicesRuffini p es la lista de las raices enteras de p, calculadas usando el regla de Ruffini. Por ejemplo,

    λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    λ> ejPol1
    3*x^4 + -5*x^2 + 3
    λ> raicesRuffini ejPol1
    []
    λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    λ> ejPol2
    x^5 + 5*x^2 + 4*x
    λ> raicesRuffini ejPol2
    [0,-1]
    λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    λ> ejPol3
    6*x^4 + 2*x
    λ> raicesRuffini ejPol3
    [0]
    λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
    λ> ejPol4
    x^3 + 2*x^2 + -1*x + -2
    λ> raicesRuffini ejPol4
    [1,-1,-2]

Leer más…

Utilizando el tipo abstracto de datos de los polinomios definir la función

   esRaizRuffini :: Int -> Polinomio Int -> Bool

tal que esRaizRuffini r p se verifica si r es una raiz de p, usando para ello el regla de Ruffini. Por ejemplo,

   λ> ejPol = consPol 4 6 (consPol 1 2 polCero)
   λ> ejPol
   6*x^4 + 2*x
   λ> esRaizRuffini 0 ejPol
   True
   λ> esRaizRuffini 1 ejPol
   False

Leer más…

Utilizando el tipo abstracto de datos de los polinomios definir las funciones

   cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
   restoRuffini    :: Int -> Polinomio Int -> Int

tales que

• cocienteRuffini r p es el cociente de dividir el polinomio p por el polinomio x-r. Por ejemplo:

     λ> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
     λ> ejPol
     x^3 + 2*x^2 + -1*x + -2
     λ> cocienteRuffini 2 ejPol
     x^2 + 4*x + 7
     λ> cocienteRuffini (-2) ejPol
     x^2 + -1
     λ> cocienteRuffini 3 ejPol
     x^2 + 5*x + 14

• restoRuffini r p es el resto de dividir el polinomio p por el polinomio x-r. Por ejemplo,

     λ> restoRuffini 2 ejPol
     12
     λ> restoRuffini (-2) ejPol
     0
     λ> restoRuffini 3 ejPol
     40

Comprobar con QuickCheck que, dado un polinomio p y un número entero r, las funciones anteriores verifican la propiedad de la división euclídea.

Leer más…

Utilizando el tipo abstracto de datos de los polinomios definir la función

   ruffiniDensa :: Int -> [Int] -> [Int]

tal que ruffiniDensa r cs es la lista de los coeficientes del cociente junto con el rsto que resulta de aplicar la regla de Ruffini para dividir el polinomio cuya representación densa es cs entre x-r. Por ejemplo,

   ruffiniDensa 2 [1,2,-1,-2] == [1,4,7,12]
   ruffiniDensa 1 [1,2,-1,-2] == [1,3,2,0]

ya que

     | 1  2  -1  -2           | 1  2  -1  -2
   2 |    2   8  14         1 |    1   3   2
   --+--------------        --+-------------
     | 1  4   7  12           | 1  3   2   0

Leer más…

Utilizando el tipo abstracto de datos de los polinomios definir la función

   terminoIndep :: (Num a, Eq a) => Polinomio  a -> a

tal que terminoIndep p es el término independiente del polinomio p. Por ejemplo,

   λ> ejPol1 = consPol 4 3 (consPol 2 5 (consPol 0 3 polCero))
   λ> ejPol1
   3*x^4 + 5*x^2 + 3
   λ> terminoIndep ejPol1
   3
   λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol2
   x^5 + 5*x^2 + 4*x
   λ> terminoIndep ejPol2
   0

Leer más…

El método de Horner para calcular el valor de un polinomio se basa en representarlo de una forma forma alernativa. Por ejemplo, para calcular el valor de

   a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f

se representa como

  (((((0 * x + a) * x + b) * x + c) * x + d) * x + e) * x + f

y se evalúa de dentro hacia afuera; es decir,

  v(0) = 0
  v(1) = v(0)*x+a = 0*x+a = a
  v(2) = v(1)*x+b = a*x+b
  v(3) = v(2)*x+c = (a*x+b)*x+c = a*x^2+b*x+c
  v(4) = v(3)*x+d = (a*x^2+b*x+c)*x+d = a*x^3+b*x^2+c*x+d
  v(5) = v(4)*x+e = (a*x^3+b*x^2+c*x+d)*x+e = a*x^4+b*x^3+c*x^2+d*x+e
  v(6) = v(5)*x+f = (a*x^4+b*x^3+c*x^2+d*x+e)*x+f = a*x^5+b*x^4+c*x^3+d*x^2+e*x+f