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

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

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

Определения [ править ]

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

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

Свойства [ править ]

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

Приложения [ править ]

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

Вычислительная сложность [ править ]

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ См., Например, Dall & Christensen (2002) .
  2. ^ Бреу и Киркпатрик (1998) ; Канг и Мюллер (2011) .
  3. ^ МакДирмид & Mueller (2011) .
  4. ^ Marathe et al. (1994) ; Мацуи (2000) .
  5. ^ Кларк, Колборн и Джонсон (1990) .
  6. ^ Raghavan & Спинрад (2003) .
  7. ^ Gräf, Штумпф и Weißenfels (1998) .
  8. Перейти ↑ Miyamoto & Matsui (2005) .

Ссылки [ править ]

  • Бентли, Джон Л .; Станат, Дональд Ф .; Уильямс, Э. Холлинс младший (1977), «Сложность поиска ближайших соседей с фиксированным радиусом», Письма об обработке информации , 6 (6): 209–212, DOI : 10.1016 / 0020-0190 (77) 90070-9 , Руководство по ремонту  0489084.
  • Бреу, Хайнц; Киркпатрик, Дэвид Г. (1998), «Распознавание графа единичного диска является NP-трудным», Computational Geometry: Theory and Applications , 9 (1-2): 3-24, DOI : 10.1016 / s0925-7721 (97) 00014- Икс.
  • Кларк, Брент Н .; Колборн, Чарльз Дж .; Джонсон, Дэвид С. (1990), «Графы единичного диска», Дискретная математика , 86 (1–3): 165–177, DOI : 10.1016 / 0012-365X (90) 90358-O.
  • Далл, Джеспер; Кристенсен, Майкл (2002), "Случайные геометрические графы", Phys. Rev. E , 66 : 016121, arXiv : cond-mat / 0203026 , Bibcode : 2002PhRvE..66a6121D , doi : 10.1103 / PhysRevE.66.016121.
  • Gräf, A .; Штумпф, М .; Вайсенфельс, G. (1998), "О окраски единичного круга графов", Algorithmica , 20 (3): 277-293, DOI : 10.1007 / PL00009196 , МР  1489033.
  • Huson, Mark L .; Сена, Arunabha (1995), "алгоритмы планирования вещания для радиосетей", Military Communications Conference, IEEE MILCOM '95 , 2 ., Стр 647-651, DOI : 10,1109 / MILCOM.1995.483546 , ISBN 0-7803-2489-7.
  • Канг, Росс Дж .; Мюллер, Тобиас (2011), «Сферы и представления графов в виде скалярных произведений», Труды двадцать седьмого ежегодного симпозиума по вычислительной геометрии (SoCG'11), 13–15 июня 2011 г., Париж, Франция , стр. 308–314.
  • Marathe, Madhav V .; Бреу, Хайнц; Хант, III, Гарри Б.; Рави, СС; Розенкранц, Дэниел Дж. (1994), Эвристика на основе геометрии для графов единичных дисков , arXiv : math.CO/9409226.
  • Matsui, Tomomi (2000), "Аппроксимация алгоритмы для максимальных независимых поставленных задач и дробной раскраска Проблемы на единичном круг графах", Lecture Notes в области компьютерных наук , Lecture Notes в области компьютерных наук, 1763 : 194-200, DOI : 10.1007 / 978-3 -540-46515-7_16 , ISBN 978-3-540-67181-7.
  • МакДиармид, Колин; Мюллер, Тобиас (2011), Целочисленные реализации дисковых и сегментных графов , arXiv : 1111.2931 , Bibcode : 2011arXiv1111.2931M
  • Миямото, Юичиро; Matsui, Tomomi (2005), "совершенство и несовершенство к - й Сила решетчатых графов" , Lecture Notes в области компьютерных наук , Lecture Notes в области компьютерных наук, 3521 : 233-242 , DOI : 10.1007 / 11496199_26 , ISBN 978-3-540-26224-4.
  • Рагхаван, Виджай; Спинрад, Джереми (2003), "Надежные алгоритмы для ограниченных областей", журнал алгоритмов , 48 (1): 160-172, DOI : 10.1016 / S0196-6774 (03) 00048-8 , MR  2006100.