Граф единичных кругов

В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.

Характеристики

Возможно несколько вариантов определения графа единичных кругов, эквивалентных с точностью до выбора коэффициента:

• Граф пересечений кругов или окружностей одинакового радиуса.
• Граф, сформированный из набора окружностей одинакового радиуса, в котором два круга соединены ребром, если центр одной окружности находится внутри другой.
• Граф, образованный из набора точек на евклидовой плоскости, в котором две точки соединены ребром, если расстояние между этими точками меньше некоторого порога.

Свойства

Любой порождённый подграф графа единичных кругов является также графом единичных кругов. Примером графа, не являющегося графом единичных кругов, служит звезда K1,7 с центральной вершиной, соединённой с семью листьями — если каждый из семи кругов касается центрального круга, какая-либо пара кругов должна касаться друг друга (поскольку контактное число на плоскости равно 6). Таким образом, граф единичных кругоов не может содержать K1,7 в качестве порождённого подграфа.

Приложения

Начиная с работы Хьюсона и Сена (Huson, Sen 1995), графы единичных кругов используются в информатике для моделирования топологии беспроводных децентрализованных самоорганизующихся сетей. В этом приложении вершины соединены прямой беспроводной связью без базовой станции. Предполагается, что все вершины однородны и снабжены всенаправленными антеннами. Расположение антенн моделируется точками на евклидовой плоскости, а область, где сигнал может быть получен другой вершиной, моделируется кругом. Если все вершины имеют передатчики одинаковой мощности, эти круги будут иметь один и тот же радиус. Случайные геометрические графы, образованные как графы единичных кругов со случайными центрами, можно использовать для моделирования фильтрации и некоторых других явлений.

Вычислительная сложность

Задача о том, можно ли представить абстрактно заданный граф в виде графа единичных кругов, является NP-трудной (точнее, полной для экзистенциальной теории вещественных чисел). Кроме того, является доказанной невозможность за полиномиальное время найти определённые координаты единичных кругов: существуют графы единичных кругов, требующие экспоненциального числа бит точности в любом таком представлении.

Однако много важных и сложных задач оптимизации на графах, таких как задача о независимом множестве, раскраска графов и задача о минимальном доминирующем множестве, можно эффективно аппроксимировать с помощью использования геометрической структуры этих графов, а задачу о клике для этих графов можно точно решить за полиномиальное время, если представление в виде кругов задано. Более точно, для заданного графа за полиномиальное время можно либо найти максимальную клику, либо доказать, что граф не является графом единичных окружностей.

Если заданное множество вершин образует подмножество треугольной решётки, необходимое и достаточное условие совершенства графа известно. Для совершенных графов многие NP-полные задачи оптимизации (задача раскраски графа, задача о максимальной клике и задача о независимом множестве) можно решить за полиномиальное время.