Граф единичных кругов
Из Википедии, бесплатной энциклопедии
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.
Характеристики[править | править код]
Возможно несколько вариантов определения графа единичных кругов, эквивалентных с точностью до выбора коэффициента:
- Граф пересечений кругов или окружностей одинакового радиуса.
- Граф, сформированный из набора окружностей одинакового радиуса, в котором два круга соединены ребром, если центр одной окружности находится внутри другой.
- Граф, образованный из набора точек на евклидовой плоскости, в котором две точки соединены ребром, если расстояние между этими точками меньше некоторого порога.
Свойства[править | править код]
Любой порождённый подграф графа единичных кругов является также графом единичных кругов. Примером графа, не являющегося графом единичных кругов, служит звезда K1,7 с центральной вершиной, соединённой с семью листьями — если каждый из семи кругов касается центрального круга, какая-либо пара кругов должна касаться друг друга (поскольку контактное число на плоскости равно 6). Таким образом, граф единичных кругоов не может содержать K1,7 в качестве порождённого подграфа.
Приложения[править | править код]
Начиная с работы Хьюсона и Сена (Huson, Sen 1995), графы единичных кругов используются в информатике для моделирования топологии беспроводных децентрализованных самоорганизующихся сетей. В этом приложении вершины соединены прямой беспроводной связью без базовой станции. Предполагается, что все вершины однородны и снабжены всенаправленными антеннами. Расположение антенн моделируется точками на евклидовой плоскости, а область, где сигнал может быть получен другой вершиной, моделируется кругом. Если все вершины имеют передатчики одинаковой мощности, эти круги будут иметь один и тот же радиус. Случайные геометрические графы, образованные как графы единичных кругов со случайными центрами, можно использовать для моделирования фильтрации и некоторых других явлений.[1]
Вычислительная сложность[править | править код]
Задача о том, можно ли представить абстрактно заданный граф в виде графа единичных кругов, является NP-трудной (точнее, полной для экзистенциальной теории вещественных чисел)[2][3]. Кроме того, является доказанной невозможность за полиномиальное время найти определённые координаты единичных кругов: существуют графы единичных кругов, требующие экспоненциального числа бит точности в любом таком представлении[4].
Однако много важных и сложных задач оптимизации на графах, таких как задача о независимом множестве, раскраска графов и задача о минимальном доминирующем множестве, можно эффективно аппроксимировать с помощью использования геометрической структуры этих графов[5][6], а задачу о клике для этих графов можно точно решить за полиномиальное время, если представление в виде кругов задано[7]. Более точно, для заданного графа за полиномиальное время можно либо найти максимальную клику, либо доказать, что граф не является графом единичных окружностей[8].
Если заданное множество вершин образует подмножество треугольной решётки, необходимое и достаточное условие совершенства графа известно[9]. Для совершенных графов многие NP-полные задачи оптимизации (задача раскраски графа, задача о максимальной клике и задача о независимом множестве) можно решить за полиномиальное время.
См. также[править | править код]
- Совокупность Виториса-Рипса, обобщение графа единичных кругов, образует конструкцию в топологическом пространстве большего порядка из единичных расстояний в метрическом пространстве.
- Граф единичных расстояний, образованный соединением точек, находящихся на расстоянии ровно единица, а не на расстоянии меньшем единицы (как в графах единичных кругов).
Примечания[править | править код]
- ↑ Смотрите, например, работу Даля и Кристенсена (Dall, Christensen 2002).
- ↑ Breu, Kirkpatrick, 1998.
- ↑ Kang, Müller, 2011.
- ↑ McDiarmid, Mueller, 2011.
- ↑ Marathe et al, 1994.
- ↑ Matsui, 2000.
- ↑ Clark, Colbourn, Johnson, 1990.
- ↑ Raghavan, Spinrad, 2003.
- ↑ 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.
 | Для улучшения этой статьи желательно:
|