El grafo completo de orden n, K(n), es un grafo no dirigido cuyos conjunto de vértices es {1,..n} y tiene una arista entre cada par de vértices distintos.
Usando el tipo abstrado de datos de los grafos, definir la función,
completo :: Int -> Grafo Int Int
tal que completo n es el grafo completo de orden n. Por ejemplo,
λ> completo 4 G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])
Un grafo es una estructura que consta de un conjunto de vértices y un conjunto de aristas que conectan los vértices entre sí. Cada vértice representa una entidad o un elemento, y cada arista representa una relación o conexión entre dos vértices.
Por ejemplo,
12 1 -------- 2 | \78 /| | \ 32/ | | \ / | 34| 5 |55 | / \ | | /44 \ | | / 93\| 3 -------- 4 61
representa un grafo no dirigido, lo que significa que las aristas tienen una dirección específica. Cada arista tiene un peso asociado, que puede representar una medida o una valoración de la relación entre los vértices que conecta.
El grafo consta de cinco vértices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los vértices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexión entre el vértice 1 y el vértice 2 con un peso de 12.
En el grafo representado, se pueden observar las conexiones entre los vértices de la siguiente manera:
Las operaciones del tipo abstracto de datos (TAD) de los grafos son
creaGrafo :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p creaGrafo' :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v)] -> Grafo v p dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v] nodos :: (Ix v,Num p) => (Grafo v p) -> [v] aristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)] aristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p
tales que
+ creaGrafo o cs as es un grafo (dirigido o no, según el de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso).
+ creaGrafo' es la versión de creaGrafo para los grafos sin pesos.
+ dirigido g se verifica si g es dirigido.
+ nodos g es la lista de todos los nodos del grafo g.
+ aristas g es la lista de las aristas del grafo g.
+ adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g.
+ aristaEn g a se verifica si a es una arista del grafo g.
+ peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.
Usando el TAD de los grafos, el grafo anterior se puede definir por
creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)]
con los siguientes argumentos:
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes: + mediante lista de adyacencia, + mediante vector de adyacencia y + mediante matriz de adyacencia.
Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.
Utilizando el tipo abstracto de datos de los polinomios definir la función
factorizacion :: Polinomio Int -> [Polinomio Int]
tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. Por ejemplo,
λ> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol1 x^5 + 5*x^2 + 4*x λ> factorizacion ejPol1 [1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4] λ> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol2 x^3 + 2*x^2 + -1*x + -2 λ> factorizacion ejPol2 [1*x + -1,1*x + 1,1*x + 2,1]
Utilizando el tipo abstracto de datos de los polinomios definir la función
raicesRuffini :: Polinomio Int -> [Int]
tal que raicesRuffini p es la lista de las raices enteras de p, calculadas usando el regla de Ruffini. Por ejemplo,
λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)) λ> ejPol1 3*x^4 + -5*x^2 + 3 λ> raicesRuffini ejPol1 [] λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol2 x^5 + 5*x^2 + 4*x λ> raicesRuffini ejPol2 [0,-1] λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero) λ> ejPol3 6*x^4 + 2*x λ> raicesRuffini ejPol3 [0] λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol4 x^3 + 2*x^2 + -1*x + -2 λ> raicesRuffini ejPol4 [1,-1,-2]
Utilizando el tipo abstracto de datos de los polinomios definir la función
esRaizRuffini :: Int -> Polinomio Int -> Bool
tal que esRaizRuffini r p se verifica si r es una raiz de p, usando para ello el regla de Ruffini. Por ejemplo,
λ> ejPol = consPol 4 6 (consPol 1 2 polCero) λ> ejPol 6*x^4 + 2*x λ> esRaizRuffini 0 ejPol True λ> esRaizRuffini 1 ejPol False
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int restoRuffini :: Int -> Polinomio Int -> Int
tales que
cocienteRuffini r p es el cociente de dividir el polinomio p por el polinomio x-r. Por ejemplo:λ> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol x^3 + 2*x^2 + -1*x + -2 λ> cocienteRuffini 2 ejPol x^2 + 4*x + 7 λ> cocienteRuffini (-2) ejPol x^2 + -1 λ> cocienteRuffini 3 ejPol x^2 + 5*x + 14
restoRuffini r p es el resto de dividir el polinomio p por el polinomio x-r. Por ejemplo,λ> restoRuffini 2 ejPol 12 λ> restoRuffini (-2) ejPol 0 λ> restoRuffini 3 ejPol 40
Comprobar con QuickCheck que, dado un polinomio p y un número entero r, las funciones anteriores verifican la propiedad de la división euclídea.
Utilizando el tipo abstracto de datos de los polinomios definir la función
ruffiniDensa :: Int -> [Int] -> [Int]
tal que ruffiniDensa r cs es la lista de los coeficientes del cociente junto con el rsto que resulta de aplicar la regla de Ruffini para dividir el polinomio cuya representación densa es cs entre x-r. Por ejemplo,
ruffiniDensa 2 [1,2,-1,-2] == [1,4,7,12] ruffiniDensa 1 [1,2,-1,-2] == [1,3,2,0]
ya que
| 1 2 -1 -2 | 1 2 -1 -2 2 | 2 8 14 1 | 1 3 2 --+-------------- --+------------- | 1 4 7 12 | 1 3 2 0
Utilizando el tipo abstracto de datos de los polinomios definir la función
terminoIndep :: (Num a, Eq a) => Polinomio a -> a
tal que terminoIndep p es el término independiente del polinomio p. Por ejemplo,
λ> ejPol1 = consPol 4 3 (consPol 2 5 (consPol 0 3 polCero)) λ> ejPol1 3*x^4 + 5*x^2 + 3 λ> terminoIndep ejPol1 3 λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol2 x^5 + 5*x^2 + 4*x λ> terminoIndep ejPol2 0
El método de Horner para calcular el valor de un polinomio se basa en representarlo de una forma forma alernativa. Por ejemplo, para calcular el valor de
a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f
se representa como
(((((0 * x + a) * x + b) * x + c) * x + d) * x + e) * x + f
y se evalúa de dentro hacia afuera; es decir,
v(0) = 0 v(1) = v(0)*x+a = 0*x+a = a v(2) = v(1)*x+b = a*x+b v(3) = v(2)*x+c = (a*x+b)*x+c = a*x^2+b*x+c v(4) = v(3)*x+d = (a*x^2+b*x+c)*x+d = a*x^3+b*x^2+c*x+d v(5) = v(4)*x+e = (a*x^3+b*x^2+c*x+d)*x+e = a*x^4+b*x^3+c*x^2+d*x+e v(6) = v(5)*x+f = (a*x^4+b*x^3+c*x^2+d*x+e)*x+f = a*x^5+b*x^4+c*x^3+d*x^2+e*x+f
Utilizando el tipo abstracto de datos de los polinomios definir la función
horner :: (Num a, Eq a) => Polinomio a -> a -> a
tal que horner p x es el valor del polinomio p al sustituir su variable por el número x. Por ejemplo,
λ> pol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> pol1 x^5 + 5*x^2 + 4*x λ> horner pol1 0 0 λ> horner pol1 1 10 λ> horner pol1 1.5 24.84375 λ> import Data.Ratio λ> horner pol1 (3%2) 795 % 32
Utilizando el tipo abstracto de datos de los polinomios definir la función
divisiblePol :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Bool
tal que divisiblePol p q se verifica si el polinomio p es divisible por el polinomio q. Por ejemplo,
λ> pol1 = consPol 2 8 (consPol 1 14 (consPol 0 3 polCero)) λ> pol1 8*x^2 + 14*x + 3 λ> pol2 = consPol 1 2 (consPol 0 3 polCero) λ> pol2 2*x + 3 λ> pol3 = consPol 2 6 (consPol 1 2 polCero) λ> pol3 6*x^2 + 2*x λ> divisiblePol pol1 pol2 True λ> divisiblePol pol1 pol3 False