مشكلة التحقيق الثنائي الأجزاء

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 8 صور
الموسوعة الحرة
يمكن أن تكون التسلسلات أعلاه بمثابة تسلسل الدرجات للرسم البياني الثنائي الأجزاء الموجود أسفله، حيث يكون لكل رأس درجة تساوي الرقم المخصص له.

تُعدّ مسألة التحقيق الثنائي مسألة قرار كلاسيكية في نظرية المخططات ، وهي فرع من فروع التوافقية . بالنظر إلى سلسلتين منتهيتين(أ1،...،أن){\displaystyle (a_{1},\dots ,a_{n})}و(ب1،...،بم){\displaystyle (b_{1},\dots ,b_{m})}من الأعداد الطبيعية معم≤ن{\displaystyle m\leq n}، تطرح المسألة السؤال التالي: هل يوجد رسم بياني ثنائي الأجزاء بسيط مُصنَّف بحيث(أ1،...،أن)،(ب1،...،بم){\displaystyle (a_{1},\dots ,a_{n}),(b_{1},\dots ,b_{m})}يمثل تسلسل الدرجات لهذا الرسم البياني الثنائي.

الحلول

تنتمي هذه المسألة إلى فئة التعقيد P. ويمكن إثبات ذلك باستخدام نظرية غيل-رايزر ، أي أنه يجب التحقق من صحةن{\displaystyle n}عدم المساواة .

ملاحظات أخرى

يمكن أيضًا صياغة المشكلة باستخدام مصفوفات ثنائية (صفر-واحد) . ويمكن ملاحظة هذا الارتباط إذا أدركنا أن لكل رسم بياني ثنائي الأجزاء مصفوفة تجاور ثنائية حيث تتوافق مجاميع الأعمدة ومجاميع الصفوف مع(أ1،...،أن){\displaystyle (a_{1},\ldots ,a_{n})}و(ب1،...،بم){\displaystyle (b_{1},\ldots ,b_{m})}غالبًا ما يُشار إلى هذه المسألة بمصفوفات ثنائية (0-1) لمجموع الصفوف والأعمدة المُعطى . في الأدبيات الكلاسيكية، كانت تُطرح المسألة أحيانًا في سياق جداول التوافق باستخدام جداول التوافق ذات الهوامش المُعطاة . أما الصياغة الثالثة فتُستخدم بدلالة متواليات درجات الرسوم البيانية الموجهة البسيطة ذات حلقة واحدة على الأكثر لكل رأس . في هذه الحالة ، تُفسَّر المصفوفة على أنها مصفوفة التجاور لهذا الرسم البياني الموجه. متى تُعتبر أزواج الأعداد الصحيحة غير السالبة (( a₁ , b₁ ), ..., ( an , bₙ ) ) أزواج درجات الدخول والخروج لرسم بياني موجه مُصنَّف ذي حلقة واحدة على الأكثر لكل رأس ؟  

تصف مسائل مشابهة متواليات درجات الرسوم البيانية البسيطة والرسوم البيانية الموجهة البسيطة. تُعرف المسألة الأولى بمسألة تحقيق الرسم البياني ، بينما تُعرف الثانية بمسألة تحقيق الرسم البياني الموجه . تُكافئ مسألة تحقيق الرسم البياني الثنائي السؤال التالي: هل يوجد رسم بياني ثنائي مُصنَّف ضمن رسم بياني ثنائي كامل لمتوالي درجات مُعطاة؟ تسأل مسألة هيتشكوك عن هذا الرسم البياني الفرعي الذي يُقلل مجموع التكاليف على كل حافة مُعطاة للرسم البياني الثنائي الكامل. تعميم آخر هو مسألة عامل f للرسوم البيانية الثنائية ، أي أنه بالنسبة لرسم بياني ثنائي مُعطى، يتم البحث عن رسم بياني فرعي يمتلك متواليات درجات مُعينة. تتمثل مسألة أخذ عينة منتظمة من رسم بياني ثنائي لمتواليات درجات ثابتة في بناء حل لمسألة تحقيق الرسم البياني الثنائي مع قيد إضافي يتمثل في أن كل حل من هذه الحلول يأتي بنفس الاحتمالية. وقد تبين أن هذه المشكلة موجودة في FPTAS للتسلسلات المنتظمة بواسطة كاثرين جرينهيل [ 1 ] (للرسوم البيانية الثنائية المنتظمة ذات العامل 1 المحظور ) وللتسلسلات شبه المنتظمة بواسطة إردوش وآخرون [ 2 ] ولا تزال المشكلة العامة غير محلولة.

الاقتباسات

مراجع