Ir al contenido principal

TAD de los grafos - Grado de un vértice

El tipo abstracto de datos de los grafos

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…

TAD de los grafos - Generadores de grafos

El tipo abstracto de datos de los grafos

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…

TAD de los grafos - Grados positivos y negativos

El tipo abstracto de datos de los grafos

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…

TAD de los grafos - Número de aristas de un grafo

El tipo abstracto de datos de los grafos

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…

TAD de los grafos - Lazos de un grafo

El tipo abstracto de datos de los grafos

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…

TAD de los grafos - Contiguos de un vértice

El tipo abstracto de datos de los grafos

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…

TAD de los grafos - Incidentes de un vértice

El tipo abstracto de datos de los grafos

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…

TAD de los grafos - Grafos ciclo

El tipo abstracto de datos de los grafos

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…

Grafos completos

El tipo abstracto de datos de los grafos

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…