{"id":5582,"date":"2020-02-19T05:30:30","date_gmt":"2020-02-19T03:30:30","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5582"},"modified":"2020-02-26T18:24:56","modified_gmt":"2020-02-26T16:24:56","slug":"nodos-y-conexiones-de-un-grafo","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/nodos-y-conexiones-de-un-grafo\/","title":{"rendered":"Nodos y conexiones de un grafo"},"content":{"rendered":"<p>Un grafo no dirigido se representa por la lista de sus arcos. Por ejemplo, el grafo<\/p>\n<pre lang=\"text\">\n             1  -- 2 -- 4\n                   | \\  |\n                   |  \\ |\n                   3 -- 5\n<\/pre>\n<p>se representa por [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)].<\/p>\n<p>Se define el tipo de grafo por<\/p>\n<pre lang=\"text\">\n   type Grafo a = [(a,a)]\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   nodos      :: Eq a => Grafo a -> [a]\n   conectados :: Eq a => Grafo a -> a -> a -> Bool\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(nodos g) es la lista de los nodos del grafo g. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nodos [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)]  ==  [1,2,3,4,5]\n<\/pre>\n<ul>\n<li>(conectados g x y) se verifica si el grafo no dirigido g posee un arco con extremos x e y. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">  \n     conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 2  ==  True\n     conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2 3  ==  True\n     conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 4  ==  False\n<\/pre>\n<p><strong>Nota<\/strong>: Escribir la soluci\u00f3n en el m\u00f3dulo <code>Grafo<\/code> para poderlo usar en los siguientes ejercicios.<\/p>\n<pre lang=\"haskell\">\nmodule Grafo where\n\nimport Data.List (nub)\n\ntype Grafo a = [(a,a)]\n\nnodos :: Eq a => Grafo a -> [a]\nnodos g = nub (concat [[x,y] | (x,y) <- g])\n\nconectados :: Eq a => Grafo a -> a -> a -> Bool\nconectados g x y =\n  (x,y) `elem` g || (y,x) `elem` g \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=\u00bbhaskell\u00bb&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<h4>Soluciones<\/h4>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\u00abLa elegancia de un teorema es directamente proporcional al n\u00famero de ideas que puedes ver en \u00e9l e inversamente proporcional al esfuerzo que requiere verlas.\u00bb <\/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>Un grafo no dirigido se representa por la lista de sus arcos. Por ejemplo, el grafo 1 &#8212; 2 &#8212; 4 | \\ | | \\ | 3 &#8212; 5 se representa por [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)]. Se define el tipo de grafo por type Grafo a = [(a,a)] Definir las funciones nodos :: Eq a => Grafo&#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":[8,12,26,24],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5582"}],"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=5582"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5582\/revisions"}],"predecessor-version":[{"id":5633,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5582\/revisions\/5633"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5582"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5582"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5582"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}