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

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