Un grafo no dirigido se representa por la lista de sus arcos. Por ejemplo, el grafo
1 -- 2 -- 4
| \ |
| \ |
3 -- 5 |
1 -- 2 -- 4
| \ |
| \ |
3 -- 5
se representa por [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)].
Se define el tipo de grafo por
Definir las funciones
nodos :: Eq a => Grafo a -> [a]
conectados :: Eq a => Grafo a -> a -> a -> Bool |
nodos :: Eq a => Grafo a -> [a]
conectados :: Eq a => Grafo a -> a -> a -> Bool
tales que
- (nodos g) es la lista de los nodos del grafo g. Por ejemplo,
nodos [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] == [1,2,3,4,5] |
nodos [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] == [1,2,3,4,5]
- (conectados g x y) se verifica si el grafo no dirigido g posee un arco con extremos x e y. Por ejemplo,
conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 2 == True
conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2 3 == True
conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 4 == False |
conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 2 == True
conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2 3 == True
conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 4 == False
Nota: Escribir la solución en el módulo Grafo
para poderlo usar en los siguientes ejercicios.
module Grafo where
import Data.List (nub)
type Grafo a = [(a,a)]
nodos :: Eq a => Grafo a -> [a]
nodos g = nub (concat [[x,y] | (x,y) <- g])
conectados :: Eq a => Grafo a -> a -> a -> Bool
conectados g x y =
(x,y) `elem` g || (y,x) `elem` g |
module Grafo where
import Data.List (nub)
type Grafo a = [(a,a)]
nodos :: Eq a => Grafo a -> [a]
nodos g = nub (concat [[x,y] | (x,y) <- g])
conectados :: Eq a => Grafo a -> a -> a -> Bool
conectados g x y =
(x,y) `elem` g || (y,x) `elem` g
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Soluciones
Pensamiento
«La elegancia de un teorema es directamente proporcional al número de ideas que puedes ver en él e inversamente proporcional al esfuerzo que requiere verlas.»
George Pólya.