مشكلة تحقيق الرسم البياني الموجه

تُعدّ مسألة تحقيق الرسم البياني الموجه مسألة قرار في نظرية الرسم البياني . بمعلومية أزواج من الأعداد الصحيحة غير السالبة${\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}$، تطرح المسألة السؤال التالي: هل يوجد رسم بياني موجه بسيط مُصنَّف بحيث يكون كل رأس${\displaystyle v_{i}}$لديه درجة داخلية${\displaystyle a_{i}}$ودرجة خارجية${\displaystyle b_{i}}$.

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

يمكن أيضًا صياغة المشكلة باستخدام مصفوفات ثنائية (صفر-واحد) . ويمكن ملاحظة هذا الارتباط إذا أدركنا أن لكل رسم بياني موجه مصفوفة تجاور حيث تتوافق مجاميع الأعمدة ومجاميع الصفوف مع${\displaystyle (a_{1},\cdots ,a_{n})}$و${\displaystyle (b_{1},\ldots ,b_{n})}$لاحظ أن قطر المصفوفة لا يحتوي إلا على أصفار. ولذلك، يُشار إلى هذه المسألة غالبًا بمصفوفات ثنائية (0-1) لمجموعات الصفوف والأعمدة المعطاة . في الأدبيات الكلاسيكية، كانت تُطرح المسألة أحيانًا في سياق جداول التوافق باستخدام جداول التوافق ذات الهوامش المعطاة .

تصف مسائل مشابهة متواليات درجات الرسوم البيانية البسيطة ، والرسوم البيانية الموجهة البسيطة ذات الحلقات ، والرسوم البيانية الثنائية البسيطة . تُعرف المسألة الأولى بمسألة تحقيق الرسم البياني . أما المسألتان الثانية والثالثة فهما متكافئتان وتُعرفان بمسألة تحقيق الرسم البياني الثنائي . قدّم تشين (1966) توصيفًا للرسوم البيانية المتعددة الموجهة ذات عدد محدود من الأقواس والحلقات المتوازية لمتوالي درجات مُعطاة . يُعرف القيد الإضافي المتمثل في عدم وجود دورات في الرسم البياني الموجه بتحقيق الرسم البياني الموجه غير الدوري (DAG) . أثبت نيشترلين وهارتونغ (2012) أن هذه المسألة من فئة NP-completeness . بيّن بيرغر ومولر -هانيمان (2011) أن فئة المتواليات المتقابلة تنتمي إلى P. تتمثل مسألة أخذ عينات منتظمة من رسم بياني موجه لمتوالي درجات ثابتة في بناء حل لمسألة تحقيق الرسم البياني الموجه مع القيد الإضافي المتمثل في أن كل حل يأتي بنفس الاحتمالية. وقد تبين أن هذه المشكلة موجودة في FPTAS للتسلسلات المنتظمة بواسطة كاثرين جرينهيل ( 2011 ) . ولا تزال المشكلة العامة غير محلولة. 

• تشين، واي كاي ( 1966)، "حول تحقيق الرسم البياني ( p ، s ) ذي الدرجات المحددة"، مجلة معهد فرانكلين ، 103 : 406-422
• نيشترلين، أندريه؛ هارتونغ، سيب ( 2012)، "صعوبة NP وقابلية معالجة المعلمات الثابتة لتحقيق متواليات الدرجة باستخدام الرسوم البيانية الموجهة غير الدورية"، مجلة معهد فرانكلين ، 7318 : 283-292
• بيرغر، أنابيل؛ مولر-هانيمان، ماتياس ( 2011)، "تحقيقات DAG لتسلسلات الدرجة الموجهة"، وقائع المؤتمر الدولي الثامن عشر حول أساسيات نظرية الحوسبة : 264-275
• غرينهيل، كاثرين (2011)، "حد متعدد الحدود لوقت الخلط لسلسلة ماركوف لأخذ عينات من الرسوم البيانية الموجهة المنتظمة"، المجلة الإلكترونية للتوافقية ، 18