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

Пусть дано множество 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. Формально задача о критическом диапазоне определяется следующим образом.

Определение 1. Критическим диапазоном для монотонного свойства графа ж над множеством точек V, обозначаемым рж (V), является наименьший диапазон r, такой, что <math>G_r (V) \;</math> обладает свойством ж.

С другой стороны, для заданного геометрического свойства соответствующая геометрическая структура обычно бывает встроена. Во многих случаях задача нахождения критического диапазона для свойства графа оказывается родственной или эквивалентной задаче о самом длинном ребре в соответствующей геометрической структуре. Например, если граф <math>G_r (V) \;</math> является связным, он содержит евклидово минимальное остовное дерево (EMST), а pcon (V) эквивалентно длине наибольшего ребра в EMST. Таким образом, задача нахождения критического диапазона для свойства связности эквивалентна задаче нахождения самого длинного ребра в EMST, а критическим диапазоном для свойства связности является наименьшее значение r, такое, что <math>G_r (V) \;</math> содержит EMST.

В большинстве случаев, как в приведенном примере, критический диапазон можно вычислить при помощи алгоритмов с полиномиальным временем выполнения. Таким образом, эта задача не является вычислительно сложной. Исследователей интересует вероятностный анализ критического диапазона, особенно асимптотическое поведение графов r-кругов над множествами случайных точек. В качестве общего термина для теории графов r-кругов над множествами случайных точек используется обозначение «случайные геометрические графы» [8].