2025-11-17T15:31:13.202496

Remoteness, order, size and connectivity constraints in digraphs

Mallu
Let \( D \) be a strongly connected digraph. The average distance of a vertex \( v \) in \( D \) is defined as the arithmetic mean of the distances from \( v \) to all other vertices in \( D \). The remoteness \( ρ(D) \) of \( D \) is the maximum of the average distances of the vertices in \( D \). In this paper, we provide a sharp upper bound on the remoteness of a strong digraph with given order, size, and vertex-connectivity. We then characterise the extremal digraphs that maximise remoteness among all strong digraphs of order \(n\), size at least \(m\), and vertex-connectivity \(κ\). Finally, we demonstrate that the upper bounds on the remoteness of a graph given its order, size, and connectivity constraints (see \cite{DanMafMal2025}) can be extended to a larger class of digraphs containing all graphs, the Eulerian digraphs.
academic

البعد، الترتيب، الحجم وقيود الاتصال في الرسوم البيانية الموجهة

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

  • معرّف الورقة: 2510.08841
  • العنوان: Remoteness, order, size and connectivity constraints in digraphs
  • المؤلف: Sufiyan Mallu (جامعة جوهانسبرج، جنوب أفريقيا)
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 13 أكتوبر 2025 (نسخة arXiv المسبقة)
  • رابط الورقة: https://arxiv.org/abs/2510.08841

الملخص

تدرس هذه الورقة مسألة البعد (remoteness) في الرسوم البيانية الموجهة القوية المتصلة. بالنسبة للرسم البياني الموجه القوي المتصل DD، يُعرّف متوسط المسافة للرأس vv بأنه المتوسط الحسابي لمسافات vv إلى جميع الرؤوس الأخرى، بينما يُعرّف البعد ρ(D)\rho(D) بأنه القيمة العظمى لمتوسط المسافات لجميع الرؤوس. تقدم الورقة حدوداً علوية محكمة للبعد في الرسوم البيانية الموجهة القوية ذات الترتيب والحجم والاتصال الرأسي المحددة، وتوصف الرسوم البيانية الموجهة الطرفية التي تعظم البعد بين جميع الرسوم البيانية الموجهة القوية ذات الترتيب nn والحجم على الأقل mm والاتصال الرأسي κ\kappa، وتثبت أن الحدود العليا للبعد في الرسوم البيانية غير الموجهة المتعلقة بقيود الترتيب والحجم والاتصال يمكن تعميمها على فئة أكبر من الرسوم البيانية الموجهة - الرسوم البيانية الموجهة الأويلرية.

الخلفية البحثية والدافع

  1. المشكلة المدروسة: على الرغم من الدراسة الواسعة لمسائل المسافة في الرسوم البيانية، فإن دراسة المسافة في الرسوم البيانية الموجهة نسبياً محدودة، خاصة فيما يتعلق باستكشاف مفاهيم القرب (proximity) والبعد في الرسوم البيانية الموجهة.
  2. أهمية المشكلة:
    • معاملات المسافة لها موقع أساسي في نظرية الرسوم البيانية، مع تطبيقات مهمة في تحليل الشبكات وتصميم الخوارزميات
    • الرسوم البيانية الموجهة تنمذج بشكل أفضل العلاقات غير المتماثلة في العالم الحقيقي، مثل شبكات النقل والشبكات الاجتماعية
    • المسائل الطرفية تحت قيود الاتصال لها قيمة نظرية مهمة
  3. حدود الطرق الموجودة:
    • قام Ai وآخرون 1 بتوسيع مفاهيم القرب والبعد إلى الرسوم البيانية الموجهة للمرة الأولى، لكن الأبحاث ذات الصلة لا تزال محدودة
    • تركز النتائج الموجودة بشكل أساسي على الحالات التي تأخذ في الاعتبار قيود الترتيب فقط، مع نقص في النتائج التي تأخذ في الاعتبار الحجم والاتصال معاً
  4. الدافع البحثي: تهدف هذه الورقة إلى سد الفجوة في نظرية البعد للرسوم البيانية الموجهة، وإنشاء حدود أكثر دقة وتوصيف الهياكل الطرفية.

المساهمات الأساسية

  1. إنشاء حدود جديدة: توفير حدود علوية محكمة للبعد في الرسوم البيانية الموجهة القوية κ\kappa-المتصلة مع ترتيب وحجم واتصال رأسي محددة
  2. توصيف الهياكل الطرفية: توصيف كامل للرسوم البيانية الموجهة الطرفية التي تحقق الحد الأعلى للبعد - الرسوم البيانية الموجهة الكاملة للمسار κ\kappa-المتصلة
  3. تعميم النتائج الموجودة: إثبات أن الحدود العليا للبعد في الرسوم البيانية غير الموجهة يمكن تعميمها على الرسوم البيانية الموجهة الأويلرية
  4. توفير إثباتات بناءة: من خلال بناء عائلات رسوم بيانية طرفية محددة، إثبات محكمية الحدود المحققة

شرح الطريقة

تعريف المهمة

الإدخال: رسم بياني موجه قوي متصل DD ومعاملاته (الترتيب nn، الحجم mm، الاتصال الرأسي κ\kappa) الإخراج: حد أعلى للبعد ρ(D)\rho(D)قيود: يجب أن يكون DD رسماً بيانياً موجهاً قوياً متصلاً κ\kappa

المفاهيم الأساسية

  1. متوسط المسافة: يُعرّف متوسط المسافة للرأس vv بـ σ(v,D)=1n−1∑w∈V(D)dD(v,w)\sigma(v,D) = \frac{1}{n-1}\sum_{w \in V(D)} d_D(v,w)
  2. البعد: يُعرّف بعد الرسم البياني الموجه بـ ρ(D)=max⁡v∈V(D)σ(v,D)\rho(D) = \max_{v \in V(D)} \sigma(v,D)
  3. الرسم البياني الموجه الكامل للمسار κ\kappa-المتصل: رسم بياني موجه بالشكل K1+←[Kκ↔]ℓ+←Ka↔+←Kb↔K_1 \overleftarrow{+} [\overleftrightarrow{K_\kappa}]^\ell \overleftarrow{+} \overleftrightarrow{K_a} \overleftarrow{+} \overleftrightarrow{K_b} حيث a≥κa \geq \kappa.

الطرق التقنية الرئيسية

  1. التحليل الطرفي: من خلال تحليل توزيع المسافات للرأس الذي يعظم البعد، إنشاء قيود هيكلية
  2. البناء الاستقرائي: إثبات تدريجي أن الرسم البياني الطرفي يجب أن يمتلك هيكل مسار كامل محدد
  3. تحسين الحجم: تحليل قيود الحجم الأقصى للرسم البياني مع الحفاظ على البعد الثابت

اللمات الرئيسية

اللمة 3.1:

  • (أ) بالنسبة لرسم بياني موجه كامل للمسار κ\kappa-متصل HH، إضافة أي قوس تقلل من بعده
  • (ب) توجد علاقة مقايضة صارمة بين الحجم والبعد بين رسمين بيانيين موجهين قويين كاملين للمسار κ\kappa-متصلين مختلفين
  • (ج) بالنظر إلى n,κn, \kappa، الشرط الضروري والكافي لوجود رسم بياني موجه كامل للمسار κ\kappa-متصل بحجم محدد

إعداد التجربة

هذه الورقة بحث نظري بحت، لا تتضمن التحقق التجريبي، بل تتحقق من صحة النتائج من خلال إثبات رياضي صارم.

استراتيجية الإثبات

  1. إثبات الوجود: بناء عائلات رسوم بيانية طرفية محددة
  2. إثبات التفرد: إثبات تفرد هيكل الرسم البياني الطرفي
  3. التحقق من المحكمية: التحقق من محكمية الحدود من خلال أمثلة محددة

النتائج الرئيسية

النظرية الأساسية

النظرية 3.2: دع DD يكون رسماً بيانياً موجهاً قوياً متصلاً بترتيب nn وحجم mm، حيث m≤n2−2n−1m \leq n^2 - 2n - 1، إذن ρ(D)≤ρ(DPKn,m,κ)\rho(D) \leq \rho(DPK_{n,m,\kappa})

عندما m≡(n2−2n−1)(modκ)m \equiv (n^2-2n-1) \pmod{\kappa} وتحت شروط محددة، تكون المساواة صحيحة إذا وفقط إذا كان D=DPKn,m,κD = DPK_{n,m,\kappa}.

الحدود المحددة

النتيجة 3.3: تحت الشروط المناسبة، ρ(D)≤nκ+2−1κ−κ−1n−1−m∗κ(n−1)\rho(D) \leq \frac{n}{\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m^*}{\kappa(n-1)}

حيث m∗m^* هو أصغر عدد صحيح يحقق m∗≥mm^* \geq m و m∗≡(n2−2n−1)(modκ)m^* \equiv (n^2-2n-1) \pmod{\kappa}.

نتائج الرسوم البيانية الموجهة الأويلرية

النظرية 4.3: دع DD يكون رسماً بيانياً موجهاً أويلرياً κ\kappa-متصلاً بترتيب nn وحجم على الأقل 2m02m_0، إذن ρ(D)≤n2κ+2−1κ−κ−1n−1−m0κ(n−1)\rho(D) \leq \frac{n}{2\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m_0}{\kappa(n-1)}

نقاط الابتكار التقني

  1. اكتمال توصيف الهيكل: ليس فقط توفير الحدود، بل توصيف كامل للهياكل الطرفية التي تحقق الحد الأعلى
  2. معالجة القيود متعددة المعاملات: النظر في ثلاثة معاملات - الترتيب والحجم والاتصال - في نفس الوقت
  3. التعميم من الرسوم البيانية غير الموجهة إلى الموجهة: استخدام ذكي لخصائص الرسوم البيانية الموجهة الأويلرية لتعميم نتائج الرسوم البيانية غير الموجهة
  4. إدخال شروط العمليات المعيارية: اكتشاف شروط العمليات المعيارية التي يجب أن يحققها معامل الحجم

الأعمال ذات الصلة

التطور التاريخي

  1. Zelinka 29 و Aouchiche, Hansen 4: إنشاء الحدود الأساسية العليا للبعد في الرسوم البيانية المتصلة ρ(G)≤n/2\rho(G) \leq n/2
  2. Ai وآخرون 1: تعميم مفهوم البعد إلى الرسوم البيانية الموجهة
  3. Entringer وآخرون 18: النظر في قيود حجم الرسم البياني
  4. Dankelmann وآخرون 15: إنشاء حدود البعد للرسوم البيانية غير الموجهة مع قيود الاتصال

موضع مساهمة هذه الورقة

هذه الورقة هي الثانية المكرسة لدراسة البعد في الرسوم البيانية الموجهة، وتسد فجوة مهمة في نظرية الرسوم البيانية الموجهة، وتعمم بنجاح النتائج الدقيقة للرسوم البيانية غير الموجهة إلى فئة أوسع من الرسوم البيانية الموجهة.

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. إنشاء حدود علوية محكمة للبعد في الرسوم البيانية الموجهة القوية κ\kappa-المتصلة
  2. توصيف كامل لهيكل الرسوم البيانية الطرفية (الرسوم البيانية الموجهة الكاملة للمسار κ\kappa-المتصلة)
  3. إثبات أن حدود البعد للرسوم البيانية غير الموجهة يمكن تعميمها على الرسوم البيانية الموجهة الأويلرية

الأهمية النظرية

  • إثراء نظرية المسافة للرسوم البيانية الموجهة
  • توفير أدوات نظرية جديدة لتحليل الشبكات
  • إنشاء جسر بين نظرية الرسوم البيانية غير الموجهة والموجهة

الاتجاهات المستقبلية

  1. دراسة البعد في فئات رسوم بيانية موجهة أكثر عمومية
  2. استكشاف العلاقات بين البعد ومعاملات الرسوم البيانية الأخرى
  3. النظر في حالة الرسوم البيانية الموجهة المرجحة

التقييم المتعمق

المميزات

  1. الاكتمال النظري: ليس فقط توفير الحدود، بل توصيف كامل للهياكل الطرفية
  2. العمق التقني: تقنيات الإثبات دقيقة، خاصة في التعامل مع تعقيد الرسوم البيانية الموجهة
  3. محكمية النتائج: جميع النتائج الرئيسية محكمة، مما يشير إلى أن الحدود مثالية
  4. براعة التعميم: طريقة تعميم نتائج الرسوم البيانية غير الموجهة إلى الرسوم البيانية الموجهة من خلال الرسوم البيانية الموجهة الأويلرية مبتكرة جداً

أوجه القصور

  1. نطاق التطبيق: النتائج نظرية بشكل أساسي، وتحتاج القيمة العملية إلى استكشاف إضافي
  2. التعقيد الحسابي: لم تتم مناقشة التعقيد الحسابي للمسائل ذات الصلة
  3. نطاق المعاملات: بعض النتائج تتطلب استيفاء شروط عمليات معيارية محددة، مما يحد من نطاق التطبيق

التأثير

  1. المساهمة النظرية: وضع أساس مهم لنظرية المسافة في الرسوم البيانية الموجهة
  2. القيمة المنهجية: قد تنطبق تقنيات الإثبات على مسائل رسوم بيانية موجهة أخرى
  3. الأبحاث اللاحقة: توفير إطار عمل لدراسة معاملات المسافة الأخرى للرسوم البيانية الموجهة

السيناريوهات المناسبة

  1. قياس المركزية في تحليل الشبكات
  2. تحليل هيكل الرسوم البيانية الموجهة
  3. بحث الرسوم البيانية الطرفية
  4. تحليل الحدود النظرية في تصميم الخوارزميات

المراجع

تستشهد الورقة بـ 29 مرجعاً ذا صلة، تغطي النتائج الرئيسية في دراسة مسائل المسافة في نظرية الرسوم البيانية، خاصة:

  • 1 العمل الرائد لـ Ai وآخرين حول القرب والبعد في الرسوم البيانية الموجهة
  • 15 أحدث نتائج Dankelmann وآخرين حول البعد في الرسوم البيانية غير الموجهة
  • 29 العمل المبكر لـ Zelinka حول البعد

التقييم الشامل: هذه ورقة عالية الجودة في النظرية، تقدم مساهمات جوهرية في مجال البعد في الرسوم البيانية الموجهة - وهو مجال بحثي مهم لكن نسبياً جديد. تتمتع الورقة بمستوى تقني عالٍ، والنتائج كاملة ومحكمة، مما يوفر أساساً متيناً للأبحاث اللاحقة في هذا المجال.