PROBLEMA "
INDEPENDENT SET" conocido como
IND-SET
Problema: Es un problema NP completo. El problema consiste en encontrar el mas largo(maximum) independent set en una grafica. Este problema de optimizacion puede ser tansformado en un problema de desicion, siguiendo el siguiente lenguaje:
INDSET = {<G,k> : G es una grafica con un independent set de tamano
k.
La grafica del problema consiste en una serie de aristas unidas por un nodo o vertice quq tienen algun color (color negro) pero algunos nodos tienen un color distinto (color rojo), y los nodos que tienen el color rojo no se pueden conectar mediante aristas, en cambio los negros si lo pueden hacer.
*Un independent set que no es el subconjunto de otro independent set es llamado:
Maximal independent set
*Independent Set : juego independiente.
*El nivel de una grafica independent set es el numero de sus aristas.
En la ciencia computacional , diversos problemas computacionales relacionados con "independent set" han sido estudiados, ejemplos:
-
Independent set Decision: aqui la entrada(input) es un grafico indirigido y un numero "
k", y la salida(output) es una exprecion booleana: verdadero si la grafica contiene un independent set de tamano
k, y falso de alguna otra manera.
-
Maximum Independent Set problem: aqui la entrada(input) es un grafico indirigido, y la salida(output) es un Maximum independent set en la grafica. Si hay varios Maximum Independent sets solo una necesitara ser la salida.
-
Maximal independent set listing problem: aqui la entrada(input) es un grafico indirigido, y la salida(output) y la salida es una lista de todos sus Maximum Independent sets. El Maximum independent set problem puede ser solucionado usando una subrutina o algoritmo para el Maximal independent set listing problem, poque el Maximun independent set debe ser incluido entre todos los Maximal independent sets.
Justificacion : despues de investigar algunas horas este problema, me preguntaba para que sirve esto?, cuales son sus aplicaciones? y aqui encontre algunas:
- sirve para la teroria de informacion/codificacion.
- para etiquetaje de mapas(map labeling).
- biologia molecular.
- Planificacion
y algunas otras mas, pero estas fueron las que me parecieron mas interesantes.
*Imagen: Map labeled(mapa etiquetado)
1- void conflict( )
2- {
3- int c=0,del=0,rm,J=0;
4- for(int i=0;i<size1;i++)
5- {
6- c=0;
7- for(int j=0;j<size1;j++)
8- if( graph[ind_set[i]][ind_set[j]]=1)
9- c++;
10- if(c>del)
11- {
12- del=c;
13- rm=ind_set[i];
14- }
15- }
16- if(del>0)
17- {
18- size1--;
19- J=0;
20- for(int i=0;i<num_node;i++)
21- if(rm!=ind_set[i] AND J<size1)
22- G1[J++]=ind_set[i];
23- for(i=0;i<J;i++)
24- ind_set[i]=G1[i];
25- size1=J;
26- conflict( );
27- }
28- }
Este es un
algoritmo para encontrar el Maximum independent Set en una grafica.
Derivaciones del problema:
- Un set es independiente si y solo si hay un
clique en las graficas complementarias.
- Un set es independiente si y solo si su complemento es un
vertex cover.
REFERENCIAS
http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29
http://mathworld.wolfram.com/IndependentSet.html
Muy
recomendada esta pag:
http://www.dharwadker.org/independent_set/
no existe ninguna 
