Polinomios

Polinomio cromático de un grafo

PorJosé A. Alonso 17-junio-201526-marzo-2022

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

   P(n,x) = x(x-1)(x-2) ... (x-(n-1))

1	P(n,x) = x(x-1)(x-2) ... (x-(n-1))

Por ejemplo,

   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

1 2	P(3,x) = x(x-1)(x-2) = x^3 - 3x^2 + 2x P(4,x) = x(x-1)(x-2)(x-3) = x^4 - 6x^3 + 11x^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,

   P(4,2) =  0 (no se puede colorear con 2 colores)
   P(4,4) = 24 (hay 24 formas de colorearlo con 4 colores)

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

   polGC:: Int -> Polinomio Int

1	polGC:: Int -> Polinomio Int

tal que (polGC n) es el polinomio cromático del grafo completo de n vértices. Por ejemplo,

   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

1 2	polGC 4 == x^4 + -6x^3 + 11x^2 + -6x polGC 5 == x^5 + -10x^4 + 35x^3 + -50x^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

   ghci> quickCheckWith (stdArgs {maxSize=7}) prop_polGC
   +++ OK, passed 100 tests.

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

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)

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)

Polinomios pares

PorJosé A. Alonso 3-abril-20151-mayo-2016

Un polinomio de coeficientes enteros se dirá par si todos sus coeficientes son números pares. Por ejemplo, el polinomio 2x³ – 4x² + 8 es par y el x² + 2x + 10 no lo es.

Definir el predicado

   parPol :: Integral a => Polinomio a -> Bool

1	parPol :: Integral a => Polinomio a -> Bool

tal que (parPol p) se verifica si p es un polinomio par. Por ejemplo,

   ghci> parPol (consPol 3 2 (consPol 2 (-4) (consPol 0 8 polCero)))
   True
   ghci> parPol (consPol 2 1 (consPol 1 2 (consPol 0 10 polCero)))
   False

ghci> parPol (consPol 3 2 (consPol 2 (-4) (consPol 0 8 polCero)))

True

ghci> parPol (consPol 2 1 (consPol 1 2 (consPol 0 10 polCero)))

False

Comprobar con QuickCheck que la suma de un polinomio con él mismo es un polinomio par.

Nota: Este ejercicio debe realizarse usando la librería I1M.Pol que se encuentra aquí y se describe aquí.

Soluciones

import I1M.PolOperaciones
import Test.QuickCheck

parPol :: Integral a => Polinomio a -> Bool
parPol p = esPolCero p || (even (coefLider p) && parPol (restoPol p))

-- La propiedad es
prop_parPol :: Integral a => Polinomio a -> Bool
prop_parPol p =
    parPol (sumaPol p p)

-- La comprobación es 
--    ghci> quickCheck prop_parPol
--    +++ OK, passed 100 tests.

import I1M.PolOperaciones

import Test.QuickCheck

parPol :: Integral a => Polinomio a -> Bool

parPol p = esPolCero p || (even (coefLider p) && parPol (restoPol p))

-- La propiedad es

prop_parPol :: Integral a => Polinomio a -> Bool

prop_parPol p =

parPol (sumaPol p p)

-- La comprobación es

-- ghci> quickCheck prop_parPol

-- +++ OK, passed 100 tests.

Cociente entero de polinomios

PorJosé A. Alonso 18-marzo-20151-mayo-2015

El cociente entero de un polinomio P(x) por un monomio axⁿ es el polinomio que se obtiene a partir de los términos de P(x) con un grado mayor o igual que n, realizando la división entera entre sus coeficientes y el coeficiente del monomio divisor y restando el valor de n al de sus grados. Por ejemplo,

El cociente entero de 4x⁴ + 6x³ + 7x² + 5x + 2 por el monomio 3x² se obtiene a partir de los términos 4x⁴ + 6x³ + 7x² realizando la división entera entre sus coeficientes y el número 3 y restando 2 a sus grados. De esta forma se obtiene x² + 2x + 2
El cociente entero de 6x⁵ + 2x⁴ + 8x³ + 5x² + 8x + 4 por el monomio 4x³ se obtiene a partir de los términos 6x⁵ + 2x⁴ + 8x³ realizando la división entera entre sus coeficientes y el número 4 y restando 3 a sus grados. De esta forma se obtiene x² + 2

Definir la función

   cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

1	cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

tal que (cocienteEntero p a n) es el cociente entero del polinomio p por el monomio de grado n y coeficiente a. Por ejemplo,

   ghci> let listaApol xs = foldr (\(n,b) -> consPol n b) polCero xs
   ghci> cocienteEntero (listaApol [(4,4),(3,6),(2,7),(1,5),(0,2)]) 3 2
   x^2 + 2*x + 2
   ghci> cocienteEntero (listaApol [(5,6),(4,2),(3,8),(2,5),(1,8),(0,4)]) 4 3
   x^2 + 2

ghci> let listaApol xs = foldr (\(n,b) -> consPol n b) polCero xs

ghci> cocienteEntero (listaApol [(4,4),(3,6),(2,7),(1,5),(0,2)]) 3 2

x^2 + 2*x + 2

ghci> cocienteEntero (listaApol [(5,6),(4,2),(3,8),(2,5),(1,8),(0,4)]) 4 3

x^2 + 2

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.

Soluciones

import I1M.Pol

cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int
cocienteEntero p a n
    | grado p < n = polCero
    | otherwise   = consPol (grado p - n) (coefLider p `div` a)
                            (cocienteEntero (restoPol p) a n)

import I1M.Pol

cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

cocienteEntero p a n

| grado p < n = polCero

| otherwise = consPol (grado p - n) (coefLider p `div` a)

(cocienteEntero (restoPol p) a n)

Polinomio cromático de un grafo

Soluciones

Polinomios pares

Soluciones

Cociente entero de polinomios

Soluciones

Entradas recientes

Buscar

Correo electrónico