Grafo complemenario
El complementario del grafo G es un grafo G’ del mismo tipo que G (dirigido o no dirigido), con el mismo conjunto de nodos y tal que dos nodos de G’ son adyacentes si y sólo si no son adyacentes en G. Los pesos de todas las aristas del complementario es igual a 0.
Definir la función
|
1 |
complementario :: Grafo Int Int -> Grafo Int Int |
tal que (complementario g) es el complementario de g. Por ejemplo,
|
1 2 3 4 |
λ> complementario (creaGrafo D (1,3) [(1,3,0),(3,2,0),(2,2,0),(2,1,0)]) G D (array (1,3) [(1,[(1,0),(2,0)]),(2,[(3,0)]),(3,[(1,0),(3,0)])]) λ> complementario (creaGrafo D (1,3) [(3,2,0),(2,2,0),(2,1,0)]) G D (array (1,3) [(1,[(1,0),(2,0),(3,0)]),(2,[(3,0)]),(3,[(1,0),(3,0)])]) |
Nota: Se usa el módulo Grafo de la librería de I1M o cualquiera de las implementaciones de grafos (GrafoConVectorDeAdyacencia o GrafoConMatrizDeAdyacencia).
Soluciones
[schedule expon=’2017-05-17′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 17 de mayo.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
[/schedule]
[schedule on=’2017-05-17′ at=»06:00″]
|
1 2 3 4 5 6 7 8 |
import I1M.Grafo complementario :: Grafo Int Int -> Grafo Int Int complementario g = creaGrafo d (1,n) [(x,y,0) | x <- xs, y <- xs, not (aristaEn g (x,y))] where d = if dirigido g then D else ND xs = nodos g n = length xs |
[/schedule]
2 Comentarios