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

Еще одна родственная задача – вычисление независимого множества. Подмножество вершин графа 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>. Здесь <math>G_k(U) \;</math> – граф, порожденный из графа G и включающий вершины, находящиеся от вершины u на расстоянии не более k переходов (обозначается <math>N_k(u) \;</math>), т.е. <math>G_k(u) \;</math> определяется на <math>N_k(u) \;</math> и содержит все ребра G, обе конечных точки которых содержатся в <math>N_k(u) \;</math>. Хорошо известно, что для графа единичных дисков <math>\alpha^{ [1] } (UDG) \le 5 \;</math> [2] и <math>\alpha^{ [2] } (UDG) \le 18 \;</math> [11].