Cliques de un grafo

José A. Alonso

21-02-2020

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]