Взвешенное связное доминирующее множество: различия между версиями

Еще одна родственная задача – вычисление независимого множества. Подмножество вершин графа G является независимым множеством, если никакие две вершины подмножества не соединены ребром. Независимое множество является максимальным, если к нему нельзя добавить ни одной вершины так, чтобы получилось независимое множество большего размера. Очевидно, что любое максимальное независимое множество является доминирующим множеством. Оно является максимальным независимым множеством, если не существует независимого множества с большим количеством вершин. Число независимости графа G, обозначаемое как a(G), представляет собой размер максимального независимого множества этого графа. k-локальное число независимости, a^(G), определяется как a^(G) = maxu2V a(Gk(u)). Здесь GK(U) – граф, порожденный из графа G и включающий вершины, находящиеся от вершины u на расстоянии не более k переходов (обозначается Nk(u)), т.е. Gk(u) определяется на Nk(u) и содержит все ребра G, обе конечных точки которых содержатся в Nk(u). Хорошо известно, что для графа единичных дисков tt'''((7DG) < 5 [2] и a[2](UDG) < 18 [11].