Критический диапазон для беспроводных сетей: различия между версиями

Пусть дано множество V. Граф с множеством вершин V, в котором между двумя вершинами имеется ребро в том и только том случае, если расстояние между ними не превышает некоторого положительного вещественного числа r, называется графом r-кругов над множеством вершин V и обозначается <math>G_r (V) \;</math>. Если <math>r1 \le r2 \;</math>, то, очевидно, <math>G_{r_1} (V) \subseteq G_{r_2} (V) \;</math>. Свойство графа является монотонным (возрастающим), если в том случае, если граф обладает таким свойством, то каждый суперграф с тем же множеством вершин также обладает этим свойством. Задача о поиске критического диапазона (или критического радиуса) заключается в том, чтобы найти некоторый минимальный диапазон r, такой, что <math>G_r (V) \;</math> обладает некоторым монотонным свойством. К примеру, свойство связности графа является монотонным и очень важным для множества приложений. Любопытно узнать, является ли <math>G_r (V) \;</math> связным. Обозначим за pcon (V) минимальный диапазон r, такой, что <math>G_r (V) \;</math> является связным. Тогда <math>G_r (V) \;</math> является связным, если <math>r \ge \rho_{con} (V) \;</math>, и несвязным в противном случае. В данном случае <math>\rho_{con} (V) \;</math> будет называться критическим диапазоном для свойства связности V. Формально задача о критическом диапазоне определяется следующим образом.