Cтраница 1
Максимальное независимое множество обладает свойством доминирования в графе в. W, либо смежна с элементом W. Действительно, если какое-то независимое множество не доминирует в графе, то существует, по крайней мере, одна вершина, не принадлежащая множеству W и не смежная с ним. Такую вершину можно включить в множество W, не нарушая его свойств. [1]
Максимальное независимое множество / о есть независимое множество, которое становится зависимым после добавления любой вершины. [2]
Максимальное независимое множество / 0 есть независимое множество, которое становится зависимым после добавления любой вершины. Заметим, что каждое независимое множество содержится в максимальном независимом множестве. [3]
Определение 2.9. Максимальное независимое множество называется базисом Гамеля. [4]
Для случая максимальных независимых множеств мы привели алгоритм, который выдает полный список всех таких множеств. [5]
Если / - максимальное независимое множество, то не может быть вершин / s /, не соединенных с / ребром, так как иначе множество / U / также было бы независимым. С другой стороны, пусть / - независимое доминирующее множество. [6]
Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф. [7]
А множества М все максимальные независимые множества, содержащиеся в А, имеют одинаковое число элементов. [8]
Мы видели, что максимальное независимое множество обязательно является доминирующим множеством. Покажите на примере, что это не обязательно так. [9]
Совершенно очевидно, что максимальное независимое множество графа О соответствует клике графа С и наоборот, где О - дополнение графа С. [10]
Теорема 2.13. В R существует максимальное независимое множество. [11]
Для проверки верхней оценки рассмотрим максимальное независимое множество 5, содержащее р0 вершин. [12]
Если / с U - максимальное независимое множество, то не может быть вершин k e 7, не соединенных с ребром, так как в противном случае множество k u / также было бы независимым, но / - максимальное по условию. Пусть / - независимое доминирующее множество. [13]
Для проверки верхней оценки рассмотрим максимальное независимое множество S, содержащее ( 30 вершин. [14]
Итак, пусть построены все максимальные независимые множества графа 6, например с помощью алгоритма, приведенного в разд. I), и пусть задана ( п X -матрица М [ т ц ], у которой т 1, ели вершина х1 принадлежит / - му максимальному независимому множеству, и тц 0 в противном случае. Каждый столбец из решения этой ЗНП соответствует определенному цвету, который может быть использован для окраски всех вершин максимального независимого множества, представленного этим столбцом. [15]