в 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’ соответствует максимальному
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
