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…