Cтраница 2
Итак, пусть построены все максимальные независимые множества графа G, например с помощью алгоритма, приведенного в разд. Каждый столбец из решения этой ЗНП соответствует определенному цвету, который может быть использован для окраски всех вершин максимального независимого множества, представленного этим столбцом. [16]
К этому моменту будут уже напечатаны все максимальные независимые множества. [17]
Как отмечалось выше, предложенный процесс получения максимального независимого множества вершин не всегда приводит к наибольшему независимому множеству. Такая процедура даст наибольшее независимое множество для графа, изображенного на рис. 3.26. Тем не менее, постройте граф, для которого она не дает наибольшего независимого множества. [18]
&, и поэтому оно не является максимальным независимым множеством. [19]
Вследствие упомянутой выше связи между кликами и максимальными независимыми множествами методы, рассматриваемые в данном разделе и описываемые на языке максимальных независимых множеств, могут быть непосредственно использованы для построения клик. [20]
Первое очевидное соображение состоит в том, что максимальные независимые множества содержатся срп-ди тупиковых: НЯ НГ. [21]
Независимое множество, содержащее w точек, называется максимальным независимым множеством. [22]
Согласно лемме 1 множество ( 2) является максимальным независимым множеством. [23]
Для графа, изображенного на рис. 4.4, число всех максимальных независимых множеств равно 15, и в матрице, приведенной ниже, они представлены столбцами; на пустых местах в матрице должны стоять нули. [24]
Заметим, что если исходить из этого определения, то базой следует называть любое максимальное независимое множество; многократно используя свойство ( Jii), можно показать, что любое независимое множество можно расширить до базы. [25]
Рассмотрим произвольный граф 0, обладающий требуемым свойством, и выделим в нем максимальное независимое множество Sr из г вершин. [26]
Один из способов нахождения наибольшего независимого множества вершин графа О ( X, Г) состоит в построении всех максимальных независимых множеств вершин и выборе из них множества с наибольшей мощностью. [27]
Один из способов нахождения наибольшего независимого множества вершин графа G ( X, Г) состоит в построении всех максимальных независимых множеств вершин и выборе из них множества с наибольшей мощностью. [28]
С другой стороны, если нам не повезло и мы выбрали на первом шаге Vi, то в результате получится максимальное независимое множество W2, состоящее из единственной вершины. Совпадение дополнения одного максимального независимого множества с другим максимальным множеством в данном примере является случайностью. На рис. 3.27 независимое множество W - vz v4 является максимальным, однако его дополнение не является независимым множеством. [29]
Вследствие упомянутой выше связи между кликами и максимальными независимыми множествами методы, рассматриваемые в данном разделе и описываемые на языке максимальных независимых множеств, могут быть непосредственно использованы для построения клик. [30]