График единичного диска
-
Определение и свойства единичных дисковых графов
- Единичный дисковый граф — это граф, в котором каждая вершина представляет собой единичный диск, а ребра соединяют центры дисков.
- Каждый индуцированный подграф единичного дискового графа также является единичным дисковым графом.
- Примеры запрещенных индуцированных подграфов включают звезду K1,6.
- Количество единичных дисковых графов на n помеченных вершинах растет экспоненциально.
-
Приложения
- Единичные дисковые графы используются в информатике для моделирования сетей беспроводной связи ad hoc.
- Случайные геометрические графы с единичными дисками применяются для моделирования перколяции и других явлений.
-
Вычислительная сложность
- Построение единичных дисковых графов возможно за линейное время с использованием хэш-таблиц.
- Определение, является ли граф единичным дисковым, является NP-сложной задачей.
- Некоторые важные задачи оптимизации графов могут быть эффективно решены с использованием геометрической структуры единичных дисковых графов.
-
См. также
- Устойчивость барьера, алгоритмическая задача о разрыве циклов в единичных дисковых графах.
- Граф безразличия, одномерный аналог единичных дисковых графов.
- График пенни, графики единичных дисков, для которых диски могут касаться друг друга, но не перекрываться.
- График монет, график контактов дисков.
- Комплекс Виеториса-Рипса, обобщение единичного дискового графа.
- График единичного расстояния, граф, образованный соединением точек на расстоянии ровно единицы.
Полный текст статьи: