Menu Close

Cliques de orden k

José A. Alonso,

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, 
--    ghci> kSubconjuntos "bcde" 2
--    ["bc","bd","be","cd","ce","de"]
--    ghci> kSubconjuntos "bcde" 3
--    ["bcd","bce","bde","cde"]
--    ghci> 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)

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

“Es mejor resolver un problema de cinco maneras diferentes, que resolver cinco problemas de una sola manera.”

George Pólya.

Medio
, ,

2 soluciones de “Cliques de orden k”

  1. Responder
    rebgongor 
    module KCliques where
 
import Grafo
import Cliques
 
kCliques :: Eq a => Grafo a -> Int -> [[a]]
kCliques g k = [xs | xs <- cliques g, length xs == k]
  2. Responder
    juabaerui 
    module KCliques where
 
import Grafo
import Cliques
 
kCliques :: Eq a => Grafo a -> Int -> [[a]]
kCliques g k = filter (y -> length y == k) (cliques g)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.