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

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

Набор окружностей единичного радиуса и соответствующий граф.

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

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

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

Свойства

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

Приложения

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

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

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

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

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

См. также

• Совокупность Виториса-Рипса^[англ.], обобщение графа единичных кругов, образует конструкцию в топологическом пространстве большего порядка из единичных расстояний в метрическом пространстве.
• Граф единичных расстояний, образованный соединением точек, находящихся на расстоянии ровно единица, а не на расстоянии меньшем единицы (как в графах единичных кругов).

Примечания

1. Смотрите, например, работу Даля и Кристенсена (Dall, Christensen 2002).
2. Breu, Kirkpatrick, 1998.
3. Kang, Müller, 2011.
4. McDiarmid, Mueller, 2011.
5. Marathe et al, 1994.
6. Matsui, 2000.
7. Clark, Colbourn, Johnson, 1990.
8. Raghavan, Spinrad, 2003.
9. Miyamoto, Matsui, 2005.

Ссылки

• Heinz Breu, David G. Kirkpatrick. Unit disk graph recognition is NP-hard // Computational Geometry Theory and Applications. — 1998. — Т. 9, вып. 1–2. — С. 3–24.
• Brent N. Clark, Charles J. Colbourn, David S. Johnson. Unit disk graphs // Discrete Mathematics. — 1990. — Т. 86, вып. 1–3. — С. 165–177. — doi:10.1016/0012-365X(90)90358-O.
• Jesper Dall, Michael Christensen. Random geometric graphs // Phys. Rev. E. — 2002. — Т. 66. — С. 016121. — doi:10.1103/PhysRevE.66.016121. — arXiv:cond-mat/0203026.
• Mark L. Huson, Arunabha Sen. Military Communications Conference, IEEE MILCOM '95. — 1995. — Т. 2. — С. 647–651. — ISBN 0-7803-2489-7. — doi:10.1109/MILCOM.1995.483546.
• Ross J. Kang, Tobias Müller. Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France. — 2011. — С. 308–314.
• Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, S. S. Ravi, Daniel J. Rosenkrantz. Geometry based heuristics for unit disk graphs. — 1994. — arXiv:math.CO/9409226.
• Tomomi Matsui. Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs // Lecture Notes in Computer Science. — 2000. — Т. 1763. — С. 194–200. — ISBN 978-3-540-67181-7. — doi:10.1007/978-3-540-46515-7_16.
• Colin McDiarmid, Tobias, Mueller. Integer realizations of disk and segment graphs. — 2011. — arXiv:1111.2931.
• Yuichiro Miyamoto, Tomomi Matsui. Perfectness and Imperfectness of the kth Power of Lattice Graphs // Lecture Notes in Computer Science. — 2005. — Т. 3521. — С. 233–242. — ISBN 978-3-540-26224-4. — doi:10.1007/11496199_26.
• Vijay Raghavan, Jeremy Spinrad. Robust algorithms for restricted domains // Journal of Algorithms. — 2003. — Т. 48, вып. 1. — С. 160–172. — doi:10.1016/S0196-6774(03)00048-8.