Generador de Instancias el Problema de Cobertura de vértices (Vertex Cover)

Sea m = |E | el número de lados y n = |V | el número de vértices. Se definen las variables binarias: xi es 1 si el vértice está en la cubierta, y 0 en otro caso. El total de variables binarias usadas en n. El objetivo consiste en minimizar

Sujeto a

• Todo lado tiene al menos un extremo en la cubierta:

ENTRADA: Grafo G.
SALIDA: El menor número k tal que exista una cobertura de vértices S para G de tamaño k.
Equivalentemente, el problema puede definirse como un problema de decisión:

ENTRADA: Grafo G y un entero positivo k.
PREGUNTA: ¿Existe una cobertura de vértices S para G de tamaño menor o igual a k?

Estructuras para representarlo
Matriz de incidencia – El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 – conectado, 0 – no conectado)
Matriz de adyacencia – El grafo está representado por una matriz cuadrada M de tamaño n2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento mx,y es 1, de lo contrario, es 0

Tomaremos como datos de entrada
vértices , aristas.




Resultados del Generador:

#include<stdio.h>
#include<time.h>
#include<string.h>
int conectado(float densidad);

main(int argc, char *argv[]){
  
  int vertices;  // Cantidad de vertices
  int aristas;
  int maxar;    // Numero maximo de aristas
  float densidad;
  int i, j, objetos=0;
  char linea[50];
  FILE *datos;
  datos = fopen(argv[1],"r");

  if(datos!=NULL){
    
    printf("\nLeyendo instancia del archivo: %s \n\n", argv[1]);
                
    do{
      
      fgets(linea, 100, datos);
      
      if(strlen(linea)==0){       
        continue;
      }
      if(linea[0]=='#'){
        
      printf("Comentario: %s \n", linea);  
      
      }
      
      if(linea[0]=='a'){
        objetos += 1;      
 printf("%s", linea);
      }
    }while(!feof(datos));             
    printf("Son %d aristas en la instancia. \n", objetos);                                      
  }
  else{
    vertices = atoi(argv[1]);
    aristas = atoi(argv[2]);
    maxar = (vertices*(vertices-1))/2;
    
    if(aristas<vertices || aristas>maxar){
      printf("\n\nError: El numero de aristas no puede ser menor al numero de vertices");
      return 0;
    }
    
    printf("Generando conexiones al azar entre %d vertices y %d aristas \n", vertices, aristas);
    
    datos = fopen("datos.txt","w");
    
    densidad = (float)(2*aristas)/(float)(vertices*(vertices-1));
    
    fprintf(datos, "i %d %d %f\n", vertices, aristas, densidad);
    fprintf(datos, "# Instancia generada para %d vertices y %d aristas \n\n", vertices, aristas);
    
    int g[vertices+1][maxar+1];
    
    printf("Maximo de aristas: %d \n", maxar);
    printf("Densidad: %f \n", densidad);
    srand(time(NULL));
    
    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);
 }   
      }                                                 
    }
  }
  return 0;
}
int conectado(float densidad){
  
  float num;
  int x;
  
  num = (rand() % 10) + 0;
  num=num/10.00;
    
  if(num>=densidad){
    x=1;
  }else{
    x=0;
  }
  return(x);     
}

Otros generadores de Instancias en Vertex Cover:
http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm
http://cs.hbg.psu.edu/benchmarks/vertex_cover.html


Referencias
cobertura de vertices