En la teoría de grafos , un estable , también conocido como unidad independiente o conjunto independiente en inglés, es un conjunto de dos cumbres en dos no adyacentes. El tamaño de un establo es igual al número de vértices que contiene.
El tamaño máximo de un establo de un gráfico, indicado I (G) , es una invariante del gráfico. Puede relacionarse con otras invariantes, por ejemplo, con el tamaño del conjunto máximo dominante , denominado dom (G) . Plaza llamada de un gráfico de G el gráfico G ' usando las mismas alturas y que tiene un borde entre dos vértices u y v si y sólo si existe un camino de longitud como máximo 2 entre u y v en G . Entonces I (G ') es menor o igual que dom (G) .
Encontrar un establo de tamaño máximo en un gráfico es un problema clásico en la teoría de la complejidad . Es NP-completo y difícil de aproximar .