2025-11-23T03:37:16.288381

Moving through Cartesian products, coronas and joins in general position

Klavžar, Krishnakumar, Kuziak et al.
The general position problem asks for large sets of vertices such that no three vertices of the set lie on a common shortest path. Recently a dynamic version of this problem was defined, called the \emph{mobile general position problem}, in which a collection of robots must visit all the vertices of the graph whilst remaining in general position. In this paper we investigate this problem in the context of Cartesian products, corona products and joins, giving upper and lower bounds for general graphs and exact values for families including grids, cylinders, Hamming graphs and prisms of trees.
academic

Движение через декартовы произведения, корон и соединения в общем положении

Основная информация

  • ID статьи: 2505.00535
  • Название: Moving through Cartesian products, coronas and joins in general position
  • Авторы: Sandi Klavžar, Aditi Krishnakumar, Dorota Kuziak, Ethan Shallcross, James Tuite, Ismael G. Yero
  • Классификация: math.CO (комбинаторика)
  • Дата публикации: 16 октября 2025 г. (версия arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2505.00535

Аннотация

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

Исследовательский контекст и мотивация

Происхождение проблемы

  1. Статическая проблема общего положения: берёт начало из геометрической головоломки Дьюдени, требующей найти максимальное множество вершин в графе, такое что никакие три вершины не лежат на одном кратчайшем пути
  2. Приложения в коммуникации роботов: предполагается, что роботы отправляют сигналы по кратчайшим путям для связи; чтобы избежать помех, необходимо гарантировать, что ни один робот не находится на кратчайшем пути между двумя другими роботами
  3. Динамические требования: навигация роботов в реальном мире является динамической, требуя движения в сети, что мотивирует рассмотрение динамической версии проблемы общего положения

Значимость исследования

  1. Теоретическая ценность: расширяет исследование традиционной проблемы общего положения в теории графов с статического на динамический случай
  2. Практические приложения: обеспечивает теоретическую основу для планирования пути и координации мобильных роботов
  3. Анализ структуры графов: углубляет понимание структуры графов путём изучения чисел движения в общем положении при различных операциях произведения графов

Основные вклады

  1. Установление базовой теоретической базы: предоставляет систематические верхние и нижние границы для чисел движения в общем положении декартовых произведений, корон и соединений
  2. Вычисление точных значений: даёт точные формулы для чисел движения в общем положении нескольких важных семейств графов, включая:
    • Декартовы произведения полных графов: Mobgp(Kn□Km)\text{Mobgp}(K_n \square K_m)
    • Сеточные графы: Mobgp(Pn□Pm)=3\text{Mobgp}(P_n \square P_m) = 3 (при n,m≥3n,m \geq 3)
    • Призмы деревьев: Mobgp(T□K2)=ℓ(T)\text{Mobgp}(T \square K_2) = \ell(T) (число листьев)
    • Частичные результаты для цилиндрических и торических графов
  3. Анализ точности границ: доказывает точность предложенных границ и предоставляет конкретные семейства графов, достигающих границы
  4. Конструктивные построения: конструирует явные множества движения в общем положении и последовательности движений для нескольких семейств графов

Подробное описание методов

Определение задачи

Множество в общем положении: подмножество вершин SS графа GG называется множеством в общем положении, если никакие три вершины из SS не лежат на одном кратчайшем пути графа GG.

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

Допустимое движение: движение робота из вершины uu в соседнюю вершину vv, обозначаемое u⇝vu \rightsquigarrow v, является допустимым тогда и только тогда, когда:

  1. в вершине vv в настоящий момент нет робота
  2. новая конфигурация после движения остаётся множеством в общем положении

Число движения в общем положении: Mobgp(G)\text{Mobgp}(G) обозначает размер максимального множества движения в общем положении графа GG.

Основные технические методы

1. Анализ границ для декартовых произведений

Для декартова произведения G□HG \square H статья устанавливает два важных нижних предела:

Предложение 2.1:

  • Mobgp(G□H)≥max⁡{Mobgp(G),Mobgp(H)}\text{Mobgp}(G \square H) \geq \max\{\text{Mobgp}(G), \text{Mobgp}(H)\}
  • Mobgp(G□H)≥max⁡{gpo(G),gpo(H)}\text{Mobgp}(G \square H) \geq \max\{\text{gp}^o(G), \text{gp}^o(H)\}

где gpo(G)\text{gp}^o(G) — число внешнего общего положения.

2. Техника послойного анализа

Использует послойную структуру декартова произведения (GG-слои и HH-слои) для анализа:

  • GG-слои: подграфы, индуцированные V(G)×{h}V(G) \times \{h\}, обозначаемые GhG^h
  • HH-слои: подграфы, индуцированные {g}×V(H)\{g\} \times V(H), обозначаемые gH{}^gH

3. Использование выпуклости

Ключевое наблюдение: слои в декартовом произведении являются выпуклыми подграфами, что означает, что кратчайшие пути внутри слоя не покидают этот слой.

4. Конструктивный метод доказательства

Для доказательства нижних границ статья использует конструктивный метод:

  1. Размещение роботов в определённых слоях
  2. Разработка конкретной последовательности движений
  3. Проверка допустимости каждого движения
  4. Доказательство того, что все вершины могут быть посещены

Технические инновации

  1. Стратегия движения между слоями: разработка методов безопасного перемещения роботов между различными слоями с сохранением свойства общего положения
  2. Использование симметрии: умелое использование симметрии графа для упрощения конструкции последовательностей движений
  3. Комбинаторно-геометрические идеи: связь проблемы движения в общем положении с проблемами положения в комбинаторной геометрии
  4. Рекурсивные конструкции: установление рекурсивных методов построения для некоторых параметризованных семейств графов

Экспериментальная установка

Методы теоретической верификации

Как чистая математическая статья, данная работа использует строгие математические доказательства вместо экспериментальной верификации:

  1. Конструктивные доказательства: доказательство нижних границ путём явного построения множеств движения в общем положении
  2. Метод от противного: доказательство верхних границ путём предположения существования большего множества и вывода противоречия
  3. Математическая индукция: использование индукции для параметризованных семейств графов
  4. Компьютерная верификация: использование компьютерного поиска для верификации результатов в сложных случаях (например, торические графы)

Анализируемые семейства графов

  1. Декартовы произведения полных графов: Kr□KsK_r \square K_s
  2. Декартовы произведения путей: Pn□PmP_n \square P_m (сеточные графы)
  3. Призмы деревьев: T□K2T \square K_2
  4. Цилиндрические графы: Cr□PsC_r \square P_s
  5. Торические графы: Cr□CsC_r \square C_s
  6. Коронные произведения: G⊙HG \odot H
  7. Соединения: G∨HG \vee H

Экспериментальные результаты

Основные теоретические результаты

1. Точные значения для декартовых произведений полных графов

Теорема 2.4: для n≥m≥1n \geq m \geq 1:

n & \text{если } m \in \{1,2\} \\ n + m - 3 & \text{если } m \geq 3 \end{cases}$$ #### 2. Результаты для сеточных графов **Теорема 3.2**: для $n,m \geq 3$, $\text{Mobgp}(P_n \square P_m) = 3$ **Теорема 3.3**: для бесконечной сетки, $\text{Mobgp}(P_\infty \square P_\infty) = 4$ #### 3. Призмы деревьев **Теорема 3.1**: для любого дерева $T$ порядка не менее 3, $\text{Mobgp}(T \square K_2) = \ell(T)$ где $\ell(T)$ обозначает число листьев дерева $T$. #### 4. Частичные результаты для цилиндрических графов **Теорема 3.4**: для $n \geq 3$: $$\text{Mobgp}(C_n \square K_2) = \begin{cases} 3 & \text{если } n = 3 \\ 2 & \text{если } n = 4 \\ 4 & \text{в остальных случаях} \end{cases}$$ #### 5. Границы для коронных произведений **Теорема 4.1**: для любых графов $G$ и $H$: $$\max\{\text{Mobgp}(G), \text{Mobgp}(H \vee K_1)\} \leq \text{Mobgp}(G \odot H) \leq \max\{n(G), \text{gp}(H \vee K_1)\}$$ #### 6. Границы для соединений графов **Теорема 4.4**: если числа клик графов $G$ и $H$ не менее 2 и они не оба являются кликами, то: $$\min\{\omega(G), \omega(H)\} + 1 \leq \text{Mobgp}(G \vee H) \leq \omega(G) + \omega(H) - 1$$ ### Точность границ Статья доказывает, что все предложенные границы являются точными, через конкретные семейства графов, достигающих эти границы: 1. **Точность нижних границ**: доказывается через $K_r \square P_s$, что границы в предложении 2.1 являются точными 2. **Точность верхних границ**: доказывается через примеры, такие как декартовы произведения звёздных графов 3. **Анализ разрывов**: доказывается, что разрыв между числом движения в общем положении и числом общего положения может быть произвольно большим ### Важные открытия 1. **Стоимость движения**: число движения в общем положении обычно строго меньше числа общего положения 2. **Зависимость от структуры**: число движения в общем положении сильно зависит от структурных характеристик графа 3. **Влияние операций произведения**: различные операции произведения графов оказывают различное влияние на число движения в общем положении ## Связанные работы ### Статическая проблема общего положения 1. **Происхождение**: геометрическая задача Дьюдени, позже введённая в теорию графов Мануэлем и Клавжаром 2. **Исследование декартовых произведений**: обширная литература по исследованию множеств общего положения в декартовых произведениях 3. **Вариантные проблемы**: связанные концепции включают внешнее общее положение, нижнее общее положение, взаимную видимость и др. ### Динамическая версия проблемы 1. **Первое определение**: впервые определена Клавжаром и др. в 2023 году 2. **Изученные семейства**: включают блочные графы, корневые произведения, графы Кнезера, одноциклические графы и др. 3. **Связанные динамические проблемы**: включают проблему движения с взаимной видимостью и др. ### Приложения в навигации роботов 1. **Проблема взаимной видимости**: приложения в навигации роботов и коммуникации 2. **Планирование пути**: связь с проблемами избежания препятствий в планировании пути роботов 3. **Распределённые алгоритмы**: связь с проблемами координации в распределённых системах роботов ## Заключение и обсуждение ### Основные выводы 1. **Систематическая база**: устанавливает систематическую теоретическую базу для чисел движения в общем положении декартовых произведений, корон и соединений 2. **Точные результаты**: получает точные значения для чисел движения в общем положении нескольких важных семейств графов 3. **Полнота границ**: предоставляет точные верхние и нижние границы и доказывает их оптимальность 4. **Методы построения**: разрабатывает общие методы для построения множеств движения в общем положении ### Ограничения 1. **Вычислительная сложность**: статья не обсуждает алгоритмическую сложность вычисления чисел движения в общем положении 2. **Общие графы**: для общих графов всё ещё отсутствуют эффективные методы вычисления чисел движения в общем положении 3. **Оптимизация динамических стратегий**: проблемы оптимизации последовательностей движений не исследованы глубоко 4. **Практические ограничения**: не рассматриваются физические ограничения реальных систем роботов ### Направления будущих исследований Статья предлагает несколько открытых проблем в разделе 5: 1. **Нетривиальные верхние границы для декартовых произведений**: поиск лучших верхних границ для $\text{Mobgp}(G \square H)$ 2. **Многомерные случаи**: исследование чисел движения в общем положении для $k$-кратных декартовых произведений $P_\infty^{\square k}$ 3. **Специальные семейства графов**: определение точных значений для цилиндрических графов $C_7 \square P_s$ и $C_{10} \square P_s$ 4. **Другие произведения графов**: исследование проблемы движения в общем положении для сильного произведения и прямого произведения 5. **Гиперкубы**: определение чисел движения в общем положении для гиперкубов ## Глубокая оценка ### Достоинства 1. **Теоретическая глубина**: предоставляет глубокий теоретический анализ проблемы движения в общем положении, устанавливая систематическую теоретическую базу 2. **Методологические инновации**: разрабатывает множество аналитических методов, включая послойный анализ, использование симметрии и конструктивные методы доказательства 3. **Полнота результатов**: не только предоставляет границы, но и доказывает точность границ с конкретными примерами, достигающими границы 4. **Ясность изложения**: статья имеет чёткую структуру, строгие доказательства и легко понимается и проверяется 5. **Важность проблемы**: исследуемая проблема имеет важное теоретическое значение и потенциальные практические приложения ### Недостатки 1. **Алгоритмический аспект**: отсутствуют эффективные алгоритмы для вычисления чисел движения в общем положении для общих графов 2. **Анализ сложности**: не обсуждается вычислительная сложность связанных проблем 3. **Практические приложения**: связь с реальными системами роботов требует дальнейшего укрепления 4. **Открытые проблемы**: остаётся много важных открытых проблем, требующих решения ### Влияние 1. **Теоретический вклад**: вносит новое направление исследований в область комбинаторики и теории графов 2. **Методологическая ценность**: предложенные аналитические методы могут быть применены к другим связанным проблемам 3. **Потенциал приложений**: предоставляет теоретическую основу для планирования пути роботов и оптимизации сетей 4. **Исследовательское вдохновение**: предложенные открытые проблемы будут стимулировать последующие исследования ### Области применения 1. **Сети роботов**: координация и планирование пути в системах множественных роботов 2. **Сенсорные сети**: развёртывание узлов датчиков и оптимизация коммуникации 3. **Сетевая безопасность**: разработка протоколов безопасной коммуникации в распределённых системах 4. **Исследования в теории графов**: теоретическая основа для исследования проблем положения в теории графов ## Список литературы Статья цитирует 32 связанных источника, включая: 1. **Основополагающие работы по проблеме общего положения**: Manuel & Klavžar (2018) 2. **Серия исследований общего положения в декартовых произведениях**: несколько статей Клавжара и др. 3. **Связанные работы по навигации роботов**: исследования приложений Альджохани, Шармы и др. 4. **Первая статья по проблеме движения в общем положении**: Klavžar и др. (2023) --- Данная статья предоставляет систематический теоретический анализ проблемы движения в общем положении, имеет важное теоретическое значение в области комбинаторики и теории графов, а также предоставляет теоретическую основу для практических приложений в навигации роботов. Хотя остаются некоторые открытые проблемы, требующие решения, установленная в статье теоретическая база и аналитические методы создают прочный фундамент для последующих исследований.