{"id":1567,"date":"2015-06-17T06:00:50","date_gmt":"2015-06-17T04:00:50","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1567"},"modified":"2022-03-26T14:32:02","modified_gmt":"2022-03-26T12:32:02","slug":"polinomio-cromatico-de-un-grafo","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/polinomio-cromatico-de-un-grafo\/","title":{"rendered":"Polinomio crom\u00e1tico de un grafo"},"content":{"rendered":"

El polinomio crom\u00e1tico de un grafo<\/a> calcula el n\u00famero de maneras en las cuales puede ser coloreado el grafo usando un n\u00famero de colores dado, de forma que dos v\u00e9rtices adyacentes no tengan el mismo color.<\/p>\n

En el caso del grafo completo de n v\u00e9rtices, su polinomio crom\u00e1tico es<\/p>\n

\n   P(n,x) = x(x-1)(x-2) ... (x-(n-1))\n<\/pre>\n
Por ejemplo,<\/p>\n
\n   P(3,x) = x(x-1)(x-2)      = x^3 - 3*x^2 + 2*x\n   P(4,x) = x(x-1)(x-2)(x-3) = x^4 - 6*x^3 + 11*x^2 - 6*x\n<\/pre>\n
Lo que significa que P(4)(x) es el n\u00famero de formas de colorear el grafo completo de 4 v\u00e9rtices con x colores. Por tanto,<\/p>\n
\n   P(4,2) =  0 (no se puede colorear con 2 colores)\n   P(4,4) = 24 (hay 24 formas de colorearlo con 4 colores)\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   polGC:: Int -> Polinomio Int\n<\/pre>\n
tal que (polGC n) es el polinomio crom\u00e1tico del grafo completo de n v\u00e9rtices. Por ejemplo,<\/p>\n
\n   polGC 4  ==  x^4 + -6*x^3 + 11*x^2 + -6*x\n   polGC 5  ==  x^5 + -10*x^4 + 35*x^3 + -50*x^2 + 24*x\n<\/pre>\n
Comprobar con QuickCheck que si el n\u00famero de colores (x) coincide con el n\u00famero de v\u00e9rtices del grafo (n), el n\u00famero de maneras de colorear el grafo es n!.<\/p>\n
Nota 1<\/strong>. Al hacer la comprobaci\u00f3n limitar el tama\u00f1o de las pruebas como se indica a continuaci\u00f3n<\/p>\n
\n   ghci> quickCheckWith (stdArgs {maxSize=7}) prop_polGC\n   +++ OK, passed 100 tests.\n<\/pre>\n
Nota 2:<\/strong> Este ejercicio debe realizarse usando \u00fanicamente las funciones de la librer\u00eda de polinomios (I1M.PolOperaciones) que se describe aqu\u00ed<\/a> y se encuentra aqu\u00ed<\/a>.<\/p>\n
Soluciones<\/h4>\n
\nimport I1M.PolOperaciones\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\npolGC :: Int -> Polinomio Int\npolGC 0 = consPol 0 1 polCero\npolGC n = polGC (n-1) `multPol` consPol 1 1 (consPol 0 (-n+1) polCero)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\npolGC2 :: Int -> Polinomio Int\npolGC2 n = multLista (map polMon [0..n-1])\n\n-- (polMon n) es el monomio x-n. Por ejemplo,\n--    polMon 3  ==  1*x + -3\npolMon:: Int -> Polinomio Int\npolMon n = consPol 1 1 (consPol 0 (-n) polCero)\n\n-- (multLista ps) es el producto de la lista de polinomios ps.\nmultLista :: [Polinomio Int] -> Polinomio Int\nmultLista []     = polUnidad\nmultLista (p:ps) = multPol p (multLista ps)\n\n-- 3\u00aa soluci\u00f3n (por plegado)\n-- =========================\n\npolGC3 :: Int -> Polinomio Int\npolGC3 n = foldl multPol polUnidad\n           [consPol 1 1 (consPol 0 (-i) polCero) | i <- [0..n-1]]\n\n-- Comprobaci\u00f3n\n-- ============\n\n-- La propiedad es\nprop_polGC :: Int -> Property\nprop_polGC n = \n    n > 0 ==> valor (polGC n) n == product [1..n]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_polGC\n--    +++ OK, passed 100 tests.\n--    (0.04 secs, 7785800 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
El polinomio crom\u00e1tico de un grafo calcula el n\u00famero de maneras en las cuales puede ser coloreado el grafo usando un n\u00famero de colores dado, de forma que dos v\u00e9rtices adyacentes no tengan el mismo color. En el caso del grafo completo de n v\u00e9rtices, su polinomio crom\u00e1tico es P(n,x) = x(x-1)(x-2) … (x-(n-1)) Por…<\/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":[265,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1567"}],"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=1567"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1567\/revisions"}],"predecessor-version":[{"id":1648,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1567\/revisions\/1648"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1567"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1567"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1567"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}