Nodos y conexiones de un grafo
Un grafo no dirigido se representa por la lista de sus arcos. Por ejemplo, el grafo
|
1 2 3 4 |
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
|
1 |
type Grafo a = [(a,a)] |
Definir las funciones
|
1 2 |
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,
|
1 |
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,
|
1 2 3 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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.»