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

Коммуникационный граф 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). Такие сети также называются гомогенными сетями.