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.
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.
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.
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
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.
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
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]
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]
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
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)])