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

Коммуникационный граф G = (V, E) над множеством беспроводных вершин V содержит ребро uv между вершинами u и v в том и только том случае, если u и v могут напрямую связываться друг с другом, т.е. находятся в пределах областей передачи друг друга. Пусть <math>d_G(u) \;</math> – степень вершины u в графе G, а <math>\Delta \;</math> – максимальная степень среди всех беспроводных вершин (т.е. <math>\Delta = max_{u \in V} \; d_G(u) \;</math>). Каждой беспроводной вершине u сопоставлена стоимость принадлежности к магистрали – c(u). Пусть <math>\delta = max_{ij \in E} \; c(i)/c(j) \;</math>, где ij – ребро между вершинами i и j, E – множество коммуникационных каналов в беспроводной сети G, а операция взятия максимума производится над всеми парами смежных вершин i и j в G. Иными словами, <math>\delta \;</math> представляет собой максимальное отношение стоимостей двух смежных вершин и может быть названо ''сглаженностью стоимостей'' сети. Если <math>\delta \;</math> ограничено некоторой небольшой константой, стоимости вершин являются ''сглаженными''. Если область передачи каждой беспроводной вершины моделируется единичным диском с этой вершиной в центре, то коммуникационный граф называют [[граф единичных дисков|графом единичных дисков]] и обозначают как UDG(V). Такие сети также называются гомогенными сетями.

Подмножество S множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина V либо принадлежит к S, либо смежна с некоторой вершиной, принадлежащей к S. Вершины S называются доминаторами, а вершины, не входящие в S – доминируемыми вершинами. Подмножество B множества V называется [[связное доминирующее множество|связным доминирующим множеством]] (СДМ), если оно является доминирующим множеством и порождает связный подграф. Следовательно, вершины подмножества В могут «общаться» друг с другом без использования вершин V - B. Доминирующее множество минимальной мощности называется [[минимальное доминирующее множество|минимальным доминирующим множеством]] (МДМ). Связное доминирующее множество минимальной мощности называется [[минимальное связное доминирующее множество|минимальным связным доминирующим множеством]] (МСДМ). Во взвешенной версии каждой вершине u сопоставлена стоимость c(u). В этом случае связное доминирующее множество B называется [[связное взвешенное доминирующее множество|взвешенным связным доминирующим множеством]] (ВСДМ). Подмножество B множества V называется [[минимальное взвешенное связное доминирующее множество|минимальным взвешенным связным доминирующим множеством]] (МВСДМ), если оно является ВСДМ с минимальной полной стоимостью. Хорошо известно, что нахождение множества МСДМ или МВДСМ оказывается NP-полной задачей, даже если G является графом единичных дисков. В работе Вана и др. рассматривались эффективные алгоритмы аппроксимации, вычисляющие магистраль с низкой стоимостью и способные успешно аппроксимировать нахождение МВСДМ. Для заданного коммуникационного графа G = (V, E, C), где V – множество вершин, E – множество ребер, а C – множество весов ребер, соответствующая задача вычисления минимального взвешенного связного доминирующего множества формулируется следующим образом.

Еще одна родственная задача – вычисление независимого множества. Подмножество вершин графа 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].