TAD de los grafos: Nodos aislados de un grafo
Dado un grafo dirigido G, diremos que un nodo está aislado si o bien de dicho nodo no sale ninguna arista o bien no llega al nodo ninguna arista. Por ejemplo, en el siguiente grafo
|
1 2 3 |
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6), (5,4),(6,2),(6,5)] |
podemos ver que del nodo 1 salen 3 aristas pero no llega ninguna, por lo que lo consideramos aislado. Así mismo, a los nodos 2 y 4 llegan aristas pero no sale ninguna, por tanto también estarán aislados.
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
aislados :: (Ix v, Num p) => Grafo v p -> [v] |
tal que aislados g es la lista de nodos aislados del grafo g. Por ejemplo,
|
1 |
aislados grafo1 == [1,2,4] |
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 |
module Grafo_Nodos_aislados_de_un_grafo where import TAD.Grafo (Grafo, Orientacion (D), adyacentes, nodos, creaGrafo') import Data.Ix (Ix) import Grafo_Incidentes_de_un_vertice (incidentes) import Test.Hspec (Spec, hspec, it, shouldBe) grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6), (5,4),(6,2),(6,5)] aislados :: (Ix v, Num p) => Grafo v p -> [v] aislados g = [n | n <- nodos g, null (adyacentes g n) || null (incidentes g n)] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ aislados grafo1 `shouldBe` [1,2,4] -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0008 seconds -- 1 example, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
from src.Grafo_Incidentes_de_un_vertice import incidentes from src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, creaGrafo_, nodos) grafo1: Grafo = creaGrafo_(Orientacion.D, (1,6), [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]) def aislados(g: Grafo) -> list[Vertice]: return [n for n in nodos(g) if not adyacentes(g, n) or not incidentes(g, n)] # Verificación # ============ def test_aislados() -> None: assert aislados(grafo1) == [1, 2, 4] print("Verificado") # La verificación es # >>> test_aislados() # Verificado |