Cotas del Problema Cobertura de Vértices

Para el problema de la cobertura de vértices necesitamos  minimizar la cantidad de nodos utilizados para cubrir la mayor cantidad de aristas en el grafo.

 

También se podría minimizar la cantidad de aristas utilizadas para cubrir el total de nodos.










La cota superior es una solucion factible para nuestro problema en este caso sería que se cubrieran todos los nodos y vértices esto seria el total vértices y el máximo de aristas permitido.

La cota inferior es una solución ideal mas aproximada a la solución óptima que se justifica con la relación de aristas en cada vértice, es el vértice que tiene la mayor cantidad de "vecinos" y la cantidad de aristas mínima permitida que recibe como argumento bajo la condición que sea mayor al número de vértices.

Código:

printf("Maximo de aristas: %d \n", maxar);
    printf("Densidad: %f \n", densidad);
    int  max=0;
    int v[vertices+1];    
    for(i=1;i<=vertices;i++)    
      {
       v[i]=0;
      }

    for(i=1;i<=vertices;i++)
     {
     for(j=i;j<=maxar;j++)
      {
       g[i][j] = conectado(densidad);  
       if(g[i][j]==1)
        {
         printf("%d - %d \n", i, j);
         fprintf(datos, "a %d - %d \n", i, j);
         v[i]=v[i]+1;
        }   
       }                                                 
      }
    for(i=1;i<=vertices;i++)    
     {
    if(max < v[i])
      {
       max=v[i];
      } 
     }
    for(i=1;i<=vertices;i++)    
     {
      if(v[i]==max)
       {
        max=i;
       }
     }
    printf("\n#Cota inferior = (%d , %d)\n",max,aristas);   
    printf("#Cota superior = (%d , %d)\n",vertices,maxar);