Menu Close

Cliques de un grafo

José A. Alonso,

Nota: En este ejercicio usaremos las mismas notaciones que en el anterior importando el módulo Grafo.

Un clique (en español, pandilla) de un grafo g es un conjunto de nodos de g tal que todos sus elementos están conectados en g.

Definir las funciones

   esClique :: Eq a => Grafo a -> [a] -> Bool
   cliques  :: Eq a => Grafo a -> [[a]]

tales que

  • (esClique g xs) se verifica si el conjunto de nodos xs del grafo g es un clique de g. Por ejemplo, 
     esClique [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] [2,3,5]  ==  True
     esClique [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] [2,3,4]  ==  False
  • (cliques g) es la lista de los cliques del grafo g. Por ejemplo, 
     λ> cliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)]
     [[],[1],[2],[1,2],[3],[2,3],[4],[2,4],
      [5],[2,5],[3,5],[2,3,5],[4,5],[2,4,5]]

Nota: Escribir la solución en el módulo Cliques para poderlo usar en los siguientes ejercicios.

Soluciones

module Cliques where
 
import Grafo
import Data.List (tails, subsequences)
 
esClique :: Eq a => Grafo a -> [a] -> Bool
esClique g xs =
  and [conectados g x y | (x,y) <- parejas xs]
 
-- (parejas xs) es la lista de las parejas formados por los elementos de
-- xs y sus siguientes en xs. Por ejemplo, 
--    parejas [1..4] == [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
parejas :: [a] -> [(a,a)]
parejas xs =
  [(x,y) | (x:ys) <- tails xs
         , y <- ys]
 
cliques :: Eq a => Grafo a -> [[a]]
cliques g =
  [xs | xs <- subsequences (nodos g)
      , esClique g xs]

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

«Para enseñar de manera efectiva, un profesor debe desarrollar un sentimiento por su asignatura; no puede hacer que sus alumnos sientan su vitalidad si no la siente él mismo. No puede compartir su entusiasmo cuando no tiene entusiasmo que compartir. La forma en que expone su tema puede ser tan importante como el tema que expone; debe sentir personalmente que es importante.»

George Pólya.

Posted in Inicial
Tagged , , ,

2 Comments

  1. rebgongor
    Responder 
    module Cliques where
 
import Grafo
import Data.List
 
esClique :: Eq a => Grafo a -> [a] -> Bool
esClique g xs = and [conectados g x y | (x,y) <- parejas xs]
 
cliques :: Eq a => Grafo a -> [[a]]
cliques g = [xs | xs <- subsequences (nodos g), esClique g xs]
 
-- Fue definida en el ejercicio anterior pero no guardada en ningún 
-- módulo, por ello repito la función de parejas.
 
parejas :: [a] -> [(a,a)]
parejas (x:xs) = [(x,y) | y <- xs] ++ parejas xs
parejas _      = []
  2. jostircar1
    Responder 
    import Grafo
import Data.List
 
esClique :: Eq a => Grafo a -> [a] -> Bool
esClique g xs = length (intersect g ys) == length ys `div` 2
  where ys = [(x,y) | x <- xs, y <- xs, x /= y]
 
cliques :: Eq a => Grafo a -> [[a]]
cliques g = [xs | xs <- subsequences (nodos g), esClique g xs]

Escribe tu solución

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