2025-11-10T03:13:59.288121

Quasi perfect codes in the cartesian product of some graphs

Mane, Shinde
An important question in the study of quasi-perfect codes is whether such codes can be constructed for all possible lengths $n$. In this paper, we address this question for specific values of $n$. First, we investigate the existence of quasi-perfect codes in the Cartesian product of a graph $G$ and a path (or cycle), assuming that $G$ admits a perfect code. Second, we explore quasi-perfect codes in the Cartesian products of two or three cycles, $C_m\square C_n$ and $C_m\square C_n\square C_l$, as well as in the Cartesian products of two or three paths, $P_m\square P_n$ and $P_m\square P_n\square P_l$.
academic

الأكواد شبه الكاملة في الضرب الديكارتي لبعض الرسوم البيانية

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

  • معرّف الورقة: 2510.13613
  • العنوان: الأكواد شبه الكاملة في الضرب الديكارتي لبعض الرسوم البيانية
  • المؤلفون: S. A. Mane, N. V. Shinde
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 15 أكتوبر 2025
  • رابط الورقة: https://arxiv.org/abs/2510.13613

الملخص

تمثل مسألة مهمة في بحث الأكواد شبه الكاملة إمكانية بناء مثل هذه الأكواد لجميع الأطوال الممكنة n. تتناول هذه الورقة هذه المسألة بالنسبة لقيم محددة من n. أولاً، تدرس وجود الأكواد شبه الكاملة في الضرب الديكارتي للرسم البياني G مع المسار (أو الدورة)، بشرط أن يعترف الرسم البياني G بكود كامل. ثانياً، تستكشف الأكواد شبه الكاملة في الضرب الديكارتي لدورتين أو ثلاث دورات Cm□CnC_m\square C_n و Cm□Cn□ClC_m\square C_n\square C_l، وكذلك في الضرب الديكارتي لمسارين أو ثلاثة مسارات Pm□PnP_m\square P_n و Pm□Pn□PlP_m\square P_n\square P_l.

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

  1. المسألة المراد حلها: يهدف هذا البحث إلى حل مسألة وجود بناء الأكواد شبه الكاملة، وخاصة طريقة منهجية لبناء الأكواد شبه الكاملة في الضرب الديكارتي للرسوم البيانية.
  2. أهمية المسألة:
    • تلعب الأكواد الكاملة دوراً أساسياً في نظرية الأكواد المصححة للأخطاء، لكنها نادرة نسبياً
    • تؤكد حدسية جولومب-ويلش عدم وجود أكواد لي الكاملة للتصحيح e > 1 بطول n ≥ 3
    • تمثل الأكواد شبه الكاملة بديلاً تقريبياً مهماً للأكواد الكاملة ذات قيمة نظرية وتطبيقية كبيرة
  3. قيود الطرق الموجودة:
    • تظل شروط وجود الأكواد شبه الكاملة صارمة جداً
    • يُعرف القليل جداً عن الأكواد شبه الكاملة ذات نصف قطر التغطية الأكبر من 3
    • يفتقد المجال إلى طرق بناء منهجية
  4. الدافع البحثي: تطوير تقنيات لبناء الأكواد شبه الكاملة في الضرب الديكارتي للرسم البياني G مع رسوم بيانية محددة، بناءً على الأكواد الكاملة في الرسم البياني G.

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

  1. اقتراح طريقة منهجية لبناء الأكواد شبه الكاملة بناءً على الأكواد الكاملة: إذا اعترف الرسم البياني G بكود e-تصحيح كامل، فيمكن بناء كود e-تصحيح شبه كامل في G□Pn أو G□Cn
  2. بناء أكواد شبه كاملة محددة متنوعة:
    • أكواد 2-تصحيح شبه كاملة في Pm□Pn□P6k-2 و Cm□Cn□C6k
    • أكواد شبه كاملة في P4□P4□P4 بناءً على الأكواد الكاملة في P2□P2□P2
  3. توسيع النتائج المعروفة: بناء أكواد شبه كاملة في Cn□Cn□Cl (3≤n≤19)، مستفيدة من الأكواد شبه الكاملة المعروفة في Cn□Cn
  4. توفير إطار نظري شامل: تحليل منهجي لطرق بناء الأكواد شبه الكاملة في الضرب الديكارتي للمسارات والدورات

شرح الطريقة

تعريف المهمة

بالنظر إلى الرسم البياني G، بناء الأكواد شبه الكاملة في الضرب الديكارتي G□Pn و G□Cn. يكون الكود D هو t-شبه كامل إذا وفقط إذا كان t-تصحيح وكان نصف قطر التغطية يساوي t+1.

طرق البناء الأساسية

1. نظرية البناء الأساسية (النظرية 3.1)

بالنسبة لكود e-تصحيح كامل D في الرسم البياني G:

  • عندما e=1: يمكن بناء كود 1-تصحيح شبه كامل في G□P3k و G□C3k
  • عندما e≥2: يمكن بناء كود e-تصحيح شبه كامل في G□P3 و G□C3

طريقة البناء:

D' = D ⊕ {1}

حيث ⊕ يمثل الضرب المباشر للمجموعات.

2. بناء التوسع ثلاثي الأبعاد (النظرية 3.2)

بالنسبة لكود 2-تصحيح كامل D1 في Pm□Pn، بناء كود 2-تصحيح شبه كامل في Pm□Pn□P6k-2:

الخطوات:

  1. تعريف D2 = (0,3) + D1 (كود مزاح)
  2. بناء D = (D1⊕{0}) ∪ (D2⊕{3})
  3. التوسع إلى أبعاد أكبر: C = ⋃(i=0 to k-1)(D1⊕{6i} ∪ D2⊕{6i+3})

3. بناء الضرب الدوري

النظرية 3.6: بناء كود 1-تصحيح شبه كامل في C3□C6□C4k

D0 = {(0,0), (1,2), (2,4)}
D1 = {(2,1), (0,3), (1,5)}
C = ⋃(i=0 to k-1)(D0⊕{4i} ∪ D1⊕{4i+2})

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

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

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

طرق التحقق

تتحقق الورقة بشكل أساسي من صحة البناء من خلال الإثبات النظري، مع دعم البحث الحسابي للحالات المحددة:

  1. التحقق النظري: إثبات الحد الأدنى للمسافة ونصف قطر التغطية للكود المبني
  2. التحقق الحسابي: بالنسبة للحالات المعقدة (مثل بعض المعاملات في النظرية 4.4)، استخدام البحث الحسابي للتحقق

مؤشرات التقييم

  • الحد الأدنى للمسافة: الحد الأدنى للمسافة بين أي كلمتي كود
  • نصف قطر التغطية: أقصى مسافة من أي رأس إلى أقرب كلمة كود
  • الخاصية شبه الكاملة: التحقق من أن نصف قطر التغطية = القدرة على التصحيح + 1

نتائج التجربة

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

  1. نتائج النظرية 3.1:
    • عندما e=1، بناء ناجح لكود 1-تصحيح شبه كامل في G□P3k و G□C3k
    • عندما e≥2، بناء ناجح لكود e-تصحيح شبه كامل في G□P3 و G□C3
  2. نتائج البناء ثلاثي الأبعاد:
    • بناء كود 2-تصحيح شبه كامل في Pm□Pn□P6k-2 (النظرية 3.2)
    • بناء كود 2-تصحيح شبه كامل في Cm□Cn□C6k (النتيجة 3.3)
  3. أمثلة محددة:
    • كود 1-تصحيح كامل في C6□C6□C2 (النظرية 4.2)
    • كود 1-تصحيح شبه كامل في C3□C6□C4k (النظرية 3.6)

جدول ملخص البناء

الرسم البياني الأساسيالرسم البياني الهدف (الضرب الديكارتي)خصائص/وصف الكود
G (يعترف بكود e-تصحيح كامل)G□Pn, G□Cnكود e-تصحيح شبه كامل
Pm□Pn, Cm□CnPm□Pn□P6k-2, Cm□Cn□C6kكود 2-تصحيح شبه كامل
Cn□CnCn□Cn□Clأكواد شبه كاملة (3≤n≤19)

تحليل الحالات

توفر الورقة عدة أمثلة بناء محددة، مثل:

  • الشكل 1 يعرض كود 1-تصحيح شبه كامل في P4□P4□P4
  • الأشكال 2-6 تعرض بناء الأكواد شبه الكاملة في مختلف الضربات الدورية

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

  1. نظرية الأكواد الكاملة: بناءً على نظرية المجموعات الحاكمة الكاملة لـ Livingston و Stout
  2. الأكواد تحت مقياس لي: اتجاه بحثي مدفوع بحدسية جولومب-ويلش
  3. بناء الأكواد شبه الكاملة: أعمال AlBdaiwi وآخرين تحت مقياس لي
  4. الأكواد في نظرية الرسوم البيانية: نظرية الأكواد المصححة للأخطاء بناءً على مسافة الرسم البياني

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

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

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

القيود

  1. تعتمد طرق البناء على وجود الأكواد الكاملة في الرسوم البيانية الأساسية
  2. بناء بعض نطاقات المعاملات لا يزال يتطلب التحقق الحسابي
  3. تطبيق طرق البناء على الضرب الديكارتي للرسوم البيانية العامة محدود

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

  1. تحديد الأعداد الصحيحة n والرسوم البيانية G2 التي يمكن من خلالها بناء أكواد شبه كاملة في الضرب الديكارتي لـ G1 مع n نسخة من G2
  2. تحديد جميع قيم المعاملات (m,n,l) التي تجعل Cm□Cn□Cl تعترف بأكواد شبه كاملة
  3. التعميم على فئات رسوم بيانية أكثر عمومية ومساحات قياس

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

المميزات

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

أوجه القصور

  1. قيود نطاق التطبيق: تنطبق الطريقة بشكل أساسي على الضرب الديكارتي للمسارات والدورات
  2. التعقيد الحسابي: يتطلب التحقق من بعض البناءات حسابات كبيرة
  3. الأمثلية: لم يتم مناقشة مسألة أمثلية الأكواد المبنية

التأثير

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

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

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

المراجع

تستشهد الورقة بـ 33 مرجعاً ذا صلة، تشمل بشكل أساسي:

  • Golomb & Welch (1970): العمل الرائد في الأكواد الكاملة تحت مقياس لي
  • AlBdaiwi & Bose (2003): أكواد لي المسافة شبه الكاملة
  • Livingston & Stout (1990): نظرية المجموعات الحاكمة الكاملة
  • عدة أبحاث حديثة حول بناء الأكواد شبه الكاملة

التقييم الشامل: هذه ورقة عالية الجودة في مجال التقاطع بين الرياضيات التوافقية ونظرية الترميز، توفر طريقة منهجية لبناء الأكواد شبه الكاملة، تتمتع بصرامة نظرية عالية وقيمة عملية كبيرة، وتضع أساساً جيداً لمزيد من التطور في هذا المجال.