Polinomio cromático de un grafo
El polinomio cromático de un grafo calcula el número de maneras en las cuales puede ser coloreado el grafo usando un número de colores dado, de forma que dos vértices adyacentes no tengan el mismo color.
En el caso del grafo completo de n vértices, su polinomio cromático es
|
1 |
P(n,x) = x(x-1)(x-2) ... (x-(n-1)) |
Por ejemplo,
|
1 2 |
P(3,x) = x(x-1)(x-2) = x^3 - 3*x^2 + 2*x P(4,x) = x(x-1)(x-2)(x-3) = x^4 - 6*x^3 + 11*x^2 - 6*x |
Lo que significa que P(4)(x) es el número de formas de colorear el grafo completo de 4 vértices con x colores. Por tanto,
|
1 2 |
P(4,2) = 0 (no se puede colorear con 2 colores) P(4,4) = 24 (hay 24 formas de colorearlo con 4 colores) |
Definir la función
|
1 |
polGC:: Int -> Polinomio Int |
tal que (polGC n) es el polinomio cromático del grafo completo de n vértices. Por ejemplo,
|
1 2 |
polGC 4 == x^4 + -6*x^3 + 11*x^2 + -6*x polGC 5 == x^5 + -10*x^4 + 35*x^3 + -50*x^2 + 24*x |
Comprobar con QuickCheck que si el número de colores (x) coincide con el número de vértices del grafo (n), el número de maneras de colorear el grafo es n!.
Nota 1. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación
|
1 2 |
ghci> quickCheckWith (stdArgs {maxSize=7}) prop_polGC +++ OK, passed 100 tests. |
Nota 2: Este ejercicio debe realizarse usando únicamente las funciones de la librería de polinomios (I1M.PolOperaciones) que se describe aquí y se encuentra aquí.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
import I1M.PolOperaciones import Test.QuickCheck -- 1ª solución -- =========== polGC :: Int -> Polinomio Int polGC 0 = consPol 0 1 polCero polGC n = polGC (n-1) `multPol` consPol 1 1 (consPol 0 (-n+1) polCero) -- 2ª solución -- =========== polGC2 :: Int -> Polinomio Int polGC2 n = multLista (map polMon [0..n-1]) -- (polMon n) es el monomio x-n. Por ejemplo, -- polMon 3 == 1*x + -3 polMon:: Int -> Polinomio Int polMon n = consPol 1 1 (consPol 0 (-n) polCero) -- (multLista ps) es el producto de la lista de polinomios ps. multLista :: [Polinomio Int] -> Polinomio Int multLista [] = polUnidad multLista (p:ps) = multPol p (multLista ps) -- 3ª solución (por plegado) -- ========================= polGC3 :: Int -> Polinomio Int polGC3 n = foldl multPol polUnidad [consPol 1 1 (consPol 0 (-i) polCero) | i <- [0..n-1]] -- Comprobación -- ============ -- La propiedad es prop_polGC :: Int -> Property prop_polGC n = n > 0 ==> valor (polGC n) n == product [1..n] -- La comprobación es -- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_polGC -- +++ OK, passed 100 tests. -- (0.04 secs, 7785800 bytes) |
Interesante publicación, ayuda mucho