تخمين شيمانسكي

مشكلة لم تُحل في الرياضيات

هل يمكن لكل تبديل على${\displaystyle n}$هل يمكن توجيه الرسم البياني المكعب الفائق الموجه ثنائي الأبعاد ذي الأبعاد n بمسارات منفصلة الحواف ؟

المزيد من المسائل غير المحلولة في الرياضيات

في الرياضيات، تنص حدسية شيمانسكي ، التي سُميت نسبةً إلى تيد إتش. شيمانسكي، ^{[ 1 ]} على أن كل تبديل على${\displaystyle n}$يمكن توجيه الرسم البياني المكعب الفائق ثنائي الاتجاه ذي الأبعاد n بمسارات منفصلة الحواف . أي، إذا كان التبديل${\displaystyle \sigma }$يطابق كل رأس${\displaystyle v}$إلى رأس آخر${\displaystyle \sigma (v)}$ثم لكل${\displaystyle v}$يوجد مسار في الرسم البياني للمكعب الفائق من${\displaystyle v}$ل${\displaystyle \sigma (v)}$بحيث لا يوجد مساران لرأسين مختلفين${\displaystyle u}$و${\displaystyle v}$استخدم نفس الحافة في نفس الاتجاه.

تم التحقق من صحة هذه الفرضية من خلال التجارب الحاسوبية.${\displaystyle n\leq 4}$^{[ 2 ]} على الرغم من أن التخمين لا يزال مفتوحًا لـ${\displaystyle n\geq 5}$في هذه الحالة، توجد تباديل تتطلب استخدام مسارات ليست أقصر المسارات من أجل التوجيه. ^{[ 3 ]}

على الرغم من أن الفرضية الكاملة لا تزال مفتوحة، فقد تم التوصل إلى عدة نتائج جزئية. أبرزها، إثبات أن المكعب الفائق قابل لإعادة الترتيب من الدرجة 2، ما يعني إمكانية تقسيم أي تبديل إلى تبديلين جزئيين، يمكن توجيه كل منهما عبر مسارات منفصلة الحواف. ^{[ 4 ]} لهذه النتيجة تطبيقات في أساليب المشاركة الزمنية والشبكات الضوئية متعددة الأطوال الموجية، حيث يمكن تحقيق مضاعفة افتراضية للحواف دون إضافة وصلات فعلية. كما توفر نتيجة قابلية إعادة الترتيب من الدرجة 2 خوارزمية تقريبية من الدرجة 2 لمسألة المسارات المنفصلة القصوى على المكعب الفائق، والتي لها تطبيقات في التحكم في الوصول للشبكات عالية السرعة.

تُظهر نتيجة ذات صلة أنه عندما تفصل بين رؤوس المصدر والهدف مستويان على الأقل في المكعب الفائق (من حيث وزن هامينغ )، توجد مجموعتان منفصلتان من المسارات غير المتداخلة رأسيًا تربط بينهما. ^{[ 5 ]} وبشكل أعم، يُفترض أنه إذا كانت رؤوس المصدر والهدف مفصولة بـ${\displaystyle r}$المستويات، ثم${\displaystyle r}$ينبغي أن توجد مثل هذه المجموعات المنفصلة الحواف. ^{[ 5 ]}

ترتبط هذه الفرضية ارتباطًا وثيقًا بقدرة التوجيه عبر الدوائر في الشبكات، والتي تُستخدم لدعم الاتصالات المتزامنة عبر أنظمة المعالجة المتعددة المتوازية وأنظمة الاتصالات. في التوجيه عبر الدوائر، يُنشأ مسار مخصص لكل زوج من المصدر والوجهة، وتُمرر البيانات عبر هذا المسار. إذا كان المكعب الفائق قابلاً لإعادة الترتيب (أي أن فرضية شيمانسكي صحيحة)، فإنه سيضمن إمكانية تلبية أي طلب توجيه تبديلي بمسارات منفصلة الحواف، مما يسمح بنقل البيانات بالتوازي بين كل زوج من المصدر والوجهة. ^{[ 4 ]}

ترتبط هذه الفرضية أيضًا باختبار الخصائص ، لا سيما في سياق اختبار رتابة الدوال المنطقية على مجال المكعب الفائق. ^{[ 5 ]} إن فهم خصائص توجيه المكعب الفائق له آثار على تطوير خوارزميات فعالة لاختبار الرتابة والمشاكل ذات الصلة في علوم الحاسوب النظرية.