# в V, и такое, что

в V, и такое, что пересечение S с множеством вершин смежных с S пусто, является независимым множеством вершин. Пример. Множества вершин (1, 2), (3, 4, 5), (4, 7), (5, 6) - независимые. Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Если Q является семейством всех независимых множеств графа G, то число ?[G]=max?S? S?Q называется числом независимости графа G, а множество S*, на котором этот максимум достигается, называется наибольшим независимым множеством. Для нашего примера ?[G]=3, а S* есть (3, 4, 5). Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф (клика). В максимальном независимом множестве нет смежных вершин, в клике все вершины попарно смежны. Максимальное независимое множество графа G соответствует клике графа G’, где G’ - дополнение графа G. Для нашего примера дополнение G’ приведено на следующем рисунке, клика графа G’ соответствует максимальному

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа