TAD de los grafos - Anchura de un grafo

José A. Alonso

13-06-2023

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

   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 abstrado de datos de los grafos, definir la función

   anchura :: Grafo Int Int -> Int

tal que (anchuraG g) es la anchura del grafo g. Por ejemplo,

   anchura grafo1  ==  4

Comprobar experimentalmente que la anchura del grafo ciclo de orden n es n-1.

Soluciones

Se usará la función grafoCiclo definida en el ejercicio Grafos ciclo.

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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

Soluciones en Python

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