Cliques de orden k
Nota: En este ejercicio usaremos las mismas notaciones que en el anterior importando el módulo Cliques.
Definir la función
kCliques :: Eq a => Grafo a -> Int -> [[a]]
tal que (kCliques g k) es la lista de los cliques del grafo g de tamaño k. Por ejemplo,
λ> kCliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 [[2,3,5],[2,4,5]] λ> kCliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2 [[1,2],[2,3],[2,4],[2,5],[3,5],[4,5]] λ> kCliques [(n,n+1) | n <- [1..100]] 3 []
Nota: Escribir la solución en el módulo KCliques para poderlo usar en los siguientes ejercicios.
Soluciones
module KCliques where import Grafo import Cliques -- 1ª definición kCliques1 :: Eq a => Grafo a -> Int -> [[a]] kCliques1 g k = [xs | xs <- cliques g , length xs == k] -- 2ª definición kCliques :: Eq a => Grafo a -> Int -> [[a]] kCliques g k = [xs | xs <- kSubconjuntos (nodos g) k , esClique g xs] -- (kSubconjuntos xs k) es la lista de los subconjuntos de xs con k -- elementos. Por ejemplo, -- λ> kSubconjuntos "bcde" 2 -- ["bc","bd","be","cd","ce","de"] -- λ> kSubconjuntos "bcde" 3 -- ["bcd","bce","bde","cde"] -- λ> kSubconjuntos "abcde" 3 -- ["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"] kSubconjuntos :: [a] -> Int -> [[a]] kSubconjuntos _ 0 = [[]] kSubconjuntos [] _ = [] kSubconjuntos (x:xs) k = [x:ys | ys <- kSubconjuntos xs (k-1)] ++ kSubconjuntos xs k -- Comparación de eficiencia -- ========================= -- λ> kCliques1 [(n,n+1) | n <- [1..20]] 3 -- [] -- (4.28 secs, 3,204,548,608 bytes) -- λ> kCliques [(n,n+1) | n <- [1..20]] 3 -- [] -- (0.01 secs, 3,075,768 bytes)