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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Набор окружностей единичного радиуса и соответствующий граф.

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

Характеристики[править | править исходный текст]

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

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

Свойства[править | править исходный текст]

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

Приложения[править | править исходный текст]

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

Вычислительная сложность[править | править исходный текст]

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

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

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

См. также[править | править исходный текст]

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

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]

  • Heinz Breu, David G. Kirkpatrick Unit disk graph recognition is NP-hard // Computational Geometry Theory and Applications. — 1998. — В. 1–2. — Т. 9. — С. 3–24..
  • Brent N. Clark, Charles J. Colbourn, David S. Johnson Unit disk graphs // Discrete Mathematics[en]. — 1990. — В. 1–3. — Т. 86. — С. 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 — arΧiv: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. — arΧiv: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. — arΧiv: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. — В. 1. — Т. 48. — С. 160–172. — DOI:10.1016/S0196-6774(03)00048-8.