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

التحرك عبر الضربات الديكارتية والتيجان والوصلات في الموضع العام

المعلومات الأساسية

  • معرّف الورقة: 2505.00535
  • العنوان: التحرك عبر الضربات الديكارتية والتيجان والوصلات في الموضع العام
  • المؤلفون: 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. مشكلة الموضع العام الثابتة: تنشأ من لغز هندسي لـ Dudeney، وتتطلب إيجاد أكبر مجموعة من الرؤوس في الرسم البياني بحيث لا تقع أي ثلاثة رؤوس على نفس أقصر مسار
  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. **إحكام الحد الأدنى**: إثبات أن الحدود في الاقتراح 2.1 محكمة من خلال $K_r \square P_s$ 2. **إحكام الحد الأعلى**: إثبات إحكام الحد الأعلى من خلال أمثلة مثل الضرب الديكارتي للرسوم البيانية النجمية 3. **تحليل الفجوة**: إثبات أن الفجوة بين رقم الموضع العام المتحرك ورقم الموضع العام يمكن أن تكون كبيرة بشكل تعسفي ### الاكتشافات المهمة 1. **تكلفة الحركة**: رقم الموضع العام المتحرك عادة ما يكون أقل بشكل صارم من رقم الموضع العام 2. **الاعتماد على البنية**: يعتمد رقم الموضع العام المتحرك بشكل كبير على خصائص بنية الرسم البياني 3. **تأثير عمليات الضرب**: لعمليات الضرب الرسومي المختلفة تأثيرات نمطية مختلفة على رقم الموضع العام المتحرك ## الأعمال ذات الصلة ### مشكلة الموضع العام الثابتة 1. **الأصل**: مشكلة Dudeney الهندسية، التي أدخلها لاحقاً Manuel و Klavžar إلى نظرية الرسوم البيانية 2. **بحث الضرب الديكارتي**: أدبيات واسعة تدرس مجموعات الموضع العام في الضربات الديكارتية 3. **مشاكل متغيرة**: مفاهيم ذات صلة مثل الموضع العام الخارجي والموضع العام السفلي والرؤية المتبادلة ### مشاكل النسخة المتحركة 1. **الاقتراح الأول**: تم تعريف مشكلة الموضع العام المتحرك لأول مرة بواسطة Klavžar وآخرون في 2023 2. **عائلات رسومية محددة**: عائلات مدروسة تشمل الرسوم البيانية الكتلية والضربات الجذرية ورسوم بيانية Kneser والرسوم البيانية أحادية الدورة 3. **مشاكل ديناميكية ذات صلة**: مشاكل الرؤية المتبادلة المتحركة وغيرها ### تطبيقات الملاحة الروبوتية 1. **مشاكل الرؤية المتبادلة**: التطبيقات في الملاحة الروبوتية والاتصالات 2. **تخطيط المسار**: الارتباط بمشاكل تجنب العوائق في تخطيط مسار الروبوت 3. **الخوارزميات الموزعة**: الارتباط بمشاكل التنسيق في أنظمة الروبوتات الموزعة ## الخلاصة والنقاش ### الاستنتاجات الرئيسية 1. **إطار منهجي**: إنشاء إطار نظري منهجي لأرقام الموضع العام المتحرك للضربات الديكارتية والتيجان والرسوم البيانية المتصلة 2. **نتائج دقيقة**: الحصول على قيم دقيقة لأرقام الموضع العام المتحرك لعائلات رسومية مهمة متعددة 3. **اكتمال الحدود**: توفير حدود محكمة عليا وسفلى وإثبات أمثليتها 4. **طرق البناء**: تطوير طرق عامة لبناء مجموعات الموضع العام المتحركة ### القيود 1. **التعقيد الحسابي**: لم تناقش الورقة التعقيد الحسابي لحساب أرقام الموضع العام المتحرك 2. **الرسوم البيانية العامة**: لا تزال الطرق الفعالة لحساب أرقام الموضع العام المتحرك للرسوم البيانية العامة ناقصة 3. **تحسين الاستراتيجيات الديناميكية**: لم يتم البحث بعمق في مشاكل تحسين استراتيجيات الحركة 4. **القيود العملية**: لم يتم النظر في القيود الفيزيائية في أنظمة الروبوتات الحقيقية ### الاتجاهات المستقبلية تقترح الورقة عدة مشاكل مفتوحة في القسم 5: 1. **حدود عليا غير تافهة للضرب الديكارتي**: البحث عن حدود أفضل لـ $\text{Mobgp}(G \square H)$ 2. **الحالات عالية الأبعاد**: دراسة أرقام الموضع العام المتحرك للضرب الديكارتي $k$-fold $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. **سلسلة الأبحاث حول الموضع العام في الضربات الديكارتية**: عدة أوراق بحثية لـ Klavžar وآخرون 3. **الأعمال ذات الصلة بملاحة الروبوتات**: أبحاث تطبيقية لـ Aljohani و Sharma وآخرون 4. **الورقة الأولى لمشكلة الموضع العام المتحرك**: Klavžar وآخرون (2023) --- توفر هذه الورقة تحليلاً نظرياً منهجياً لمشكلة الموضع العام المتحرك، وتتمتع بقيمة نظرية مهمة في مجالات الرياضيات التوافقية ونظرية الرسوم البيانية، وتوفر في الوقت نفس أساساً نظرياً لتطبيقات ملاحة الروبوتات العملية. على الرغم من وجود بعض المشاكل المفتوحة التي تنتظر الحل، فإن الإطار النظري وطرق التحليل التي أنشأتها الورقة توفر أساساً صلباً للأبحاث اللاحقة.