Введение
График пересечения единичных дисков в плоскости
В геометрической теории графов, граф единичных дисков — это график пересечения семейства единичных дисков на евклидовой плоскости. Иными словами, это граф, имеющий по одной вершине для каждого диска в семействе, и ребро между двумя вершинами, если соответствующие диски пересекаются или находятся на расстоянии не более единицы друг от друга. Такие графы часто формируются из процесса Пуассона, что делает их простым примером случайной структуры.
Свойства
Каждый индуцированный подграф графа единичных дисков также является графом единичных дисков. Примером графа, который не является графом единичных дисков, служит звезда с одним центральным узлом, соединенным с шестью листьями: если каждый из шести единичных дисков касается общего единичного диска, то некоторые два из этих шести дисков должны касаться друг друга. Следовательно, графы единичных дисков не могут содержать индуцированный подграф в виде звезды с шестью листьями. Известно бесконечно много других запрещенных индуцированных подграфов. Количество графов единичных дисков на помеченных вершинах отличается не более чем на экспоненциальный фактор от . Этот быстрый рост означает, что графы единичных дисков не имеют ограниченной двойной ширины.
Приложения
Начиная с работ , графы единичных дисков использовались в информатике для моделирования топологии самоорганизующихся беспроводных сетей связи. В этом применении узлы соединяются напрямую по беспроводной связи без использования базовой станции. Предполагается, что все узлы однородны и оснащены всенаправленными антеннами. Положения узлов моделируются как евклидовы точки, а область, в пределах которой сигнал от одного узла может быть принят другим узлом, моделируется кругом. Если все узлы имеют передатчики одинаковой мощности, то все эти круги имеют одинаковый радиус. Случайные геометрические графы, построенные как графы единичных дисков со случайным расположением центров дисков, также использовались в качестве модели перколяции и различных других явлений.
Комплексность вычислений
Если задана коллекция единичных дисков (или их центров) в пространстве любой фиксированной размерности, можно построить соответствующий граф единичных дисков за линейное время, округляя центры до ближайших точек целочисленной решетки, используя хеш-таблицу для поиска всех пар центров, находящихся на постоянном расстоянии друг от друга, и фильтруя полученный список пар, оставляя только те, чьи окружности пересекаются. Отношение числа пар, рассматриваемых этим алгоритмом, к числу ребер в конечном графе является константой, что обеспечивает линейную временную сложность. Однако эта константа растет экспоненциально с увеличением размерности. Задача определения, может ли заданный граф (без геометрической информации) быть представлен как граф единичных дисков, является NP-трудной (точнее, полной для экзистенциальной теории вещественных чисел). Кроме того, невозможно за полиномиальное время получить явные координаты представления графа единичных дисков: существуют графы единичных дисков, которым для любого такого представления требуется экспоненциальное количество бит точности. Однако многие важные и сложные задачи оптимизации графов, такие как поиск максимального независимого множества, раскраска графов и минимального доминирующего множества, могут быть эффективно аппроксимированы с использованием геометрической структуры этих графов, а задача поиска максимальной клики может быть решена точно за полиномиальное время, при наличии представления в виде дисков. Даже если представление в виде дисков неизвестно и на вход подается абстрактный граф, за полиномиальное время можно либо найти максимальную клику, либо доказать, что граф не является графом единичных дисков, а также приближенно решить задачу раскраски графа с помощью жадного алгоритма раскраски.