Граф единичного диска

Коллекция единичных кругов и соответствующий граф единичного диска.

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

Обычно они формируются на основе точечного процесса Пуассона , что делает их простым примером случайной структуры.

Определения

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

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

Свойства

Каждый индуцированный подграф единичного дискового графа также является единичным дисковым графом. Примером графа, который не является графом единичного диска, является звезда $K_{1,6}$ с одним центральным узлом, соединенным с шестью листьями: если каждый из шести единичных дисков касается общего единичного диска, то некоторые два из шести дисков должны касаться друг друга. Следовательно, графы единичного диска не могут содержать индуцированную $K_{1,6}$ подграф. Известно бесконечно много других запрещенных индуцированных подграфов.

Количество единичных дисковых графов на $n$ помеченных вершин находится в пределах экспоненциального коэффициента $n^{2n}$. Этот быстрый рост означает, что графы единичных дисков не имеют ограниченной ширины двойника .

Приложения

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

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

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

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

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

См. также

• Барьерная устойчивость , алгоритмическая проблема разрыва циклов в графах единичного диска
• Граф безразличия , одномерный аналог графов единичного диска
• Граф Пенни , графы единичных дисков, для которых диски могут касаться, но не перекрываться ( контактный граф ).
• Граф монет , контактный граф дисков (не обязательно единичного размера).
• Комплекс Виеториса – Рипса , обобщение графа единичного диска, которое строит топологические пространства более высокого порядка из единичных расстояний в метрическом пространстве.
• Граф единичных расстояний — график, образованный соединением точек, находящихся на расстоянии ровно одной, а не (как здесь) не более чем заданного порога.

Ссылки

• Атминас, Аистис; Замараев, Виктор (2018), «О запрещенных индуцированных подграфах для единичных дисковых графов», Discrete & Computational Geometry , 60 (1): 57–97, arXiv : 1602.08148 , doi : 10.1007/s00454-018-9968-1 , MR   3807349 , S2CID   254025741
• Бентли, Джон Л .; Станат, Дональд Ф.; Уильямс, Э. Холлинз-младший (1977), «Сложность поиска ближайших соседей с фиксированным радиусом», Information Processing Letters , 6 (6): 209–212, doi : 10.1016/0020-0190(77)90070-9 , МР   0489084 .
• Бонне, Эдуард; Женье, Колин; Ким, Ын Юнг; Томассе, Стефан; Ватригант, Реми (2022), «Двойная ширина II: малые классы», Комбинаторная теория , 2 (2): P10:1–P10:42, arXiv : 2006.09877 , doi : 10.5070/C62257876 , MR   4449818
• Бреу, Хайнц; Киркпатрик, Дэвид Г. (1998), «Распознавание графов единичного диска является NP-сложным», Вычислительная геометрия: теория и приложения , 9 (1–2): 3–24, doi : 10.1016/s0925-7721(97)00014- х .
• Кларк, Брент Н.; Колборн, Чарльз Дж .; Джонсон, Дэвид С. (1990), «Графы единичных дисков», Discrete Mathematics , 86 (1–3): 165–177, doi : 10.1016/0012-365X(90)90358-O .
• Далл, Джеспер; Кристенсен, Майкл (2002), «Случайные геометрические графики», Physical Review E , 66 (1): 016121, arXiv : cond-mat/0203026 , Bibcode : 2002PhRvE..66a6121D , doi : 10.1103/PhysRevE.66.016121 , PMID   122 41440 , S2CID   15193516 .
• Дембский, Михал; Юноша-Шанявский, Константин; Слешиньска-Новак, Малгожата (2020), «Сильный хроматический индекс $K_{1,t}$-свободные графы», Дискретная прикладная математика , 284 : 53–60, doi : 10.1016/j.dam.2020.03.024 , MR   4115456 , S2CID   216369782
• Греф, А.; Стамп, М.; Вайсенфельс, Г. (1998), «О раскраске дисковых графов единиц», Algorithmica , 20 (3): 277–293, doi : 10.1007/PL00009196 , MR   1489033 , S2CID   36161020 .
• Хьюсон, Марк Л.; Сен, Арунабха (1995), «Алгоритмы планирования вещания для радиосетей», Конференция по военной связи, IEEE MILCOM '95 , том. 2, стр. 647–651, номер документа : 10.1109/MILCOM.1995.483546 , ISBN.  0-7803-2489-7 , S2CID   62039740 .
• Канг, Росс Дж.; Мюллер, Тобиас (2011), «Сферические представления и скалярные произведения графов», Труды двадцать седьмого ежегодного симпозиума по вычислительной геометрии (SoCG'11), 13–15 июня 2011 г., Париж, Франция , стр. 308–314. .
• Маратхе, Мадхав В.; Бреу, Хайнц; Хант, III, Гарри Б.; Рави, СС; Розенкранц, Дэниел Дж. (1994), Эвристика на основе геометрии для графов единичных дисков , arXiv : math.CO/9409226 , Bibcode : 1994math......9226M .
• Мацуи, Томоми (2000), «Алгоритмы аппроксимации для задач максимального независимого множества и задач дробной раскраски на единичных дисковых графах», Дискретная и вычислительная геометрия , Конспекты лекций по информатике, том. 1763, стр. 194–200, doi : 10.1007/978-3-540-46515-7_16 , ISBN.  978-3-540-67181-7 .
• МакДиармид, Колин; Мюллер, Тобиас (2013), «Целочисленные реализации дисковых и сегментных графов», Журнал комбинаторной теории , серия B, 103 (1): 114–143, arXiv : 1111.2931 , Bibcode : 2011arXiv1111.2931M , doi : 10.1016/j. jctb.2012.09.004
• МакДиармид, Колин; Мюллер, Тобиас (2014), «Число дисковых графов», Европейский журнал комбинаторики , 35 : 413–431, doi : 10.1016/j.ejc.2013.06.037 , MR   3090514
• Рагхаван, Виджай; Спинрад, Джереми (2003), «Надежные алгоритмы для ограниченных областей», Journal of Algorithms , 48 ​​(1): 160–172, doi : 10.1016/S0196-6774(03)00048-8 , MR   2006100 , S2CID   16327087 .