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 , de los cuales no hay dos adyacentes. Es decir, es un conjunto de vértices tal que por cada dos vértices de , no hay una 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 un clique en el complemento del grafo. 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 del mayor tamaño posible para un gráfico dado . Este tamaño se denomina número de independencia de y generalmente se denota por . [2] El problema de optimización de encontrar un conjunto de este tipo se denomina problema del conjunto máximo independiente. 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.
Todo conjunto independiente máximo también es máximo, pero la implicación inversa no se cumple necesariamente.
Un conjunto es independiente si y solo si es un clique en el complemento del grafo , por lo que los dos conceptos son complementarios. De hecho, los gráficos suficientemente grandes sin camarillas grandes tienen grandes conjuntos independientes, un tema que se explora en la teoría de Ramsey .
Un conjunto es independiente si y sólo si su complemento es una cubierta de vértices . [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.
