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
