Conjunto independiente (teoría de grafos)
En la teoría de grafos , un conjunto independiente , conjunto estable , coclique o anticlique es un conjunto de vértices en un gráfico , no hay dos de los cuales son adyacentes. Es decir, es un conjunto de vértices tal que por cada dos vértices adentro , no hay arista que los conecte. De manera equivalente, cada borde del gráfico tiene como máximo un punto final en . Un conjunto es independiente si y solo si es una camarilla en el complemento de la gráfica. El tamaño de un conjunto independiente es el número de vértices que contiene. Los conjuntos independientes también se han denominado "conjuntos internamente estables", de los cuales "conjunto estable" es una abreviatura. [1]
Un conjunto independiente máximo es un conjunto independiente que no es un subconjunto propio de ningún otro conjunto independiente.
Un conjunto independiente máximo es un conjunto independiente de mayor tamaño posible para un gráfico dado . Este tamaño se llama número de independencia de y generalmente se denota por . [2] El problema de optimización de encontrar tal conjunto se denomina problema de conjunto independiente máximo. Es un problema fuertemente NP-difícil . [3] Como tal, es poco probable que exista un algoritmo eficiente para encontrar un conjunto máximo independiente de un gráfico.
Cada conjunto máximo independiente también es máximo, pero la implicación inversa no se cumple necesariamente.
Un conjunto es independiente si y solo si es una camarilla en el complemento del gráfico , por lo que los dos conceptos son complementarios. De hecho, los gráficos suficientemente grandes sin grandes camarillas tienen grandes conjuntos independientes, un tema que se explora en la teoría de Ramsey .
Un conjunto es independiente si y solo si su complemento es una cobertura de vértice . [4] Por lo tanto, la suma del tamaño del conjunto independiente más grande y el tamaño de una cobertura mínima de vértices es igual al número de vértices en el gráfico.
