Menu Close

Grafo complemenario

José A. Alonso,

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

   complementario :: Grafo Int Int -> Grafo Int Int

tal que (complementario g) es el complementario de g. Por ejemplo,

   λ> 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

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
Ejercicio

2 soluciones de “Grafo complemenario”

  1. Responder
    albcercid 
     
complementario :: Grafo Int Int ->  Grafo Int Int
complementario g | dirigido g = creaGrafo D (x,y) [(a,b,0) | a <- t,
                                                             b <- t,
                                                             not $ aristaEn g (a,b)]
                 | otherwise = creaGrafo ND (x,y) [(a,b,0) | a <- [x..y],
                                                             b <- [a..y],
                                                             not $ aristaEn g (a,b)]
                   where x = minimum t
                         y = maximum t
                         t = nodos g
  2. Responder
    Juanjo Ortega (juaorture) 
    import I1M.Grafo
 
complementario :: Grafo Int Int -> Grafo Int Int
complementario g | dirigido g = creaGrafo D (x, lxs) [(a,b,0) | a <- ng
                                                              , b <- ng
                                                              , not (aristaEn g (a,b))]
                 | otherwise = creaGrafo ND (x, lxs) [(a,b,0) | a <- ng
                                                              , b <- ng
                                                              , not (aristaEn g (a,b))
                                                              , not (aristaEn g (b,a))]
                where ng@(x:xs) = nodos g
                      lxs = last xs

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.