6. Внутренне устойчивое множество. Число внутренней устойчивости. Оценки числа внутренней устойчивости (теоремы).

Рассмотрим неориентированный граф G = (V,E).

Независимое множество вершин (известное также как внутренне устойчивое множество) есть множество вершин графа G, такое, что любые две вершины в нем не смежны (никакая пара вершин не соединена ребром). Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Если Q является семейством всех независимых множеств графа G, то число α(G) = max |S| (S ∈ Q) называется числом независимости графа G, а множество S, на котором этот максимум достигается, называется наибольшим независимым множеством.