TAD de los grafos: Anchura de un grafo
En un grafo, la anchura de un nodo es el máximo de los absolutos de la diferencia entre el valor del nodo y los de sus adyacentes; y la anchura del grafo es la máxima anchura de sus nodos. Por ejemplo, en el grafo
|
1 2 3 4 5 |
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5), (2,4),(2,5), (3,4),(3,5), (4,5)] |
su anchura es 4 y el nodo de máxima anchura es el 5.
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
anchura :: Grafo Int Int -> Int |
tal que (anchuraG g) es la anchura del grafo g. Por ejemplo,
|
1 |
anchura grafo1 == 4 |
Comprobar experimentalmente que la anchura del grafo ciclo de orden n es n-1.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
module Grafo_Anchura_de_un_grafo where import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, aristas, creaGrafo', nodos) import Grafo_Grafos_ciclos (grafoCiclo) import Test.Hspec (Spec, hspec, it, shouldBe) grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5), (2,4),(2,5), (3,4),(3,5), (4,5)] -- 1ª solución -- =========== anchura :: Grafo Int Int -> Int anchura g = maximum [anchuraN g x | x <- nodos g] -- (anchuraN g x) es la anchura del nodo x en el grafo g. Por ejemplo, -- anchuraN g 1 == 4 -- anchuraN g 2 == 3 -- anchuraN g 4 == 2 -- anchuraN g 5 == 4 anchuraN :: Grafo Int Int -> Int -> Int anchuraN g x = maximum (0 : [abs (x-v) | v <- adyacentes g x]) -- 2ª solución -- =========== anchura2 :: Grafo Int Int -> Int anchura2 g = maximum [abs (x-y) | ((x,y),_) <- aristas g] -- La conjetura conjetura :: Int -> Bool conjetura n = anchura (grafoCiclo n) == n-1 -- La comprobación es -- λ> and [conjetura n | n <- [2..10]] -- True -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ anchura grafo1 `shouldBe` 4 it "e2" $ anchura g2 `shouldBe` 2 where g2 :: Grafo Int Int g2 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0004 seconds -- 2 examples, 0 failures |
|
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 46 47 48 49 |
from src.Grafo_Grafos_ciclos import grafoCiclo from src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, aristas, creaGrafo_, nodos) grafo1: Grafo = creaGrafo_(Orientacion.D, (1,5), [(1,2),(1,3),(1,5), (2,4),(2,5), (3,4),(3,5), (4,5)]) # 1ª solución # =========== def anchura(g: Grafo) -> int: return max(anchuraN(g, x) for x in nodos(g)) # (anchuraN g x) es la anchura del nodo x en el grafo g. Por ejemplo, # anchuraN g 1 == 4 # anchuraN g 2 == 3 # anchuraN g 4 == 2 # anchuraN g 5 == 4 def anchuraN(g: Grafo, x: Vertice) -> int: return max([0] + [abs (x - v) for v in adyacentes(g, x)]) # 2ª solución # =========== def anchura2(g: Grafo) -> int: return max(abs (x-y) for ((x,y),_) in aristas(g)) # La conjetura def conjetura(n: int) -> bool: return anchura(grafoCiclo(n)) == n - 1 # La comprobación es # >>> all(conjetura(n) for n in range(2, 11)) # True # Verificación # ============ def test_anchura() -> None: g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(1,3),(2,3),(3,3)]) assert anchura(grafo1) == 4 assert anchura(g2) == 2 print("Verificado") # La verificación es # >>> test_anchura() # Verificado |