{"id":5589,"date":"2020-02-21T05:30:52","date_gmt":"2020-02-21T03:30:52","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5589"},"modified":"2020-02-28T07:50:40","modified_gmt":"2020-02-28T05:50:40","slug":"cliques-de-un-grafo","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/cliques-de-un-grafo\/","title":{"rendered":"Cliques de un grafo"},"content":{"rendered":"<p>Nota: En este ejercicio usaremos las mismas notaciones que en el anterior importando el m\u00f3dulo <code>Grafo<\/code>.<\/p>\n<p>Un <a href=\"http:\/\/bit.ly\/31YQAKS\">clique<\/a> (en espa\u00f1ol, pandilla) de un grafo g es un conjunto de nodos de g tal que todos sus elementos est\u00e1n conectados en g.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   esClique :: Eq a => Grafo a -> [a] -> Bool\n   cliques  :: Eq a => Grafo a -> [[a]]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(esClique g xs) se verifica si el conjunto de nodos xs del grafo g es un clique de g. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">  \n     esClique [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] [2,3,5]  ==  True\n     esClique [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] [2,3,4]  ==  False\n<\/pre>\n<ul>\n<li>(cliques g) es la lista de los cliques del grafo g. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> cliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)]\n     [[],[1],[2],[1,2],[3],[2,3],[4],[2,4],\n      [5],[2,5],[3,5],[2,3,5],[4,5],[2,4,5]]\n<\/pre>\n<p><strong>Nota<\/strong>: Escribir la soluci\u00f3n en el m\u00f3dulo <code>Cliques<\/code> para poderlo usar en los siguientes ejercicios.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nmodule Cliques where\n\nimport Grafo\nimport Data.List (tails, subsequences)\n\nesClique :: Eq a => Grafo a -> [a] -> Bool\nesClique g xs =\n  and [conectados g x y | (x,y) <- parejas xs]\n\n-- (parejas xs) es la lista de las parejas formados por los elementos de\n-- xs y sus siguientes en xs. Por ejemplo, \n--    parejas [1..4] == [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]\nparejas :: [a] -> [(a,a)]\nparejas xs =\n  [(x,y) | (x:ys) <- tails xs\n         , y <- ys]\n\ncliques :: Eq a => Grafo a -> [[a]]\ncliques g =\n  [xs | xs <- subsequences (nodos g)\n      , esClique g xs]\n<\/pre>\n<h4>Otras soluciones<\/h4>\n<ul>\n<li>Se pueden escribir otras soluciones en los comentarios.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\"haskell\"&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\"Para ense\u00f1ar 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 \u00e9l 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.\" <\/p>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/George_P%C3%B3lya\">George P\u00f3lya<\/a>.\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Nota: En este ejercicio usaremos las mismas notaciones que en el anterior importando el m\u00f3dulo Grafo. Un clique (en espa\u00f1ol, pandilla) de un grafo g es un conjunto de nodos de g tal que todos sus elementos est\u00e1n conectados en g. Definir las funciones esClique :: Eq a => Grafo a -> [a] -> Bool&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[100,8,88,75],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5589"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=5589"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5589\/revisions"}],"predecessor-version":[{"id":5635,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5589\/revisions\/5635"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5589"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5589"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5589"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}