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

تُعدّ مسألة تحقيق الرسم البياني مسألة قرار في نظرية الرسم البياني . بالنظر إلى متتالية منتهية${\displaystyle (d_{1},\dots ,d_{n})}$بالنسبة للأعداد الطبيعية، تسأل المسألة عما إذا كان هناك رسم بياني بسيط مُصنَّف بحيث${\displaystyle (d_{1},\dots ,d_{n})}$يمثل تسلسل الدرجات لهذا الرسم البياني.

في سياق تحديد المواقع، قد تشير مشكلة تحقيق الرسم البياني أيضًا إلى إيجاد مجموعة من المواضع${\displaystyle (x_{1},\dots ,x_{n})}$في فضاء إقليدي ما بحيث تكون مربعات المسافات بين المواضع، معطاة بواسطة${\displaystyle d_{ij}^{2}}$قم بمطابقة أوزان الحواف${\displaystyle w_{ij}}$لجميع الحواف في رسم بياني غير مكتمل وغير موجه وموزون. ^{[ 1 ]}

يمكن حل هذه المسألة في وقت متعدد الحدود . إحدى طرق إثبات ذلك هي استخدام خوارزمية هافيل-هاكيمي لبناء حل خاص باستخدام خوارزمية تكرارية . ^{[ 2 ] [ 3 ]} بدلاً من ذلك، وباتباع التوصيف الوارد في نظرية إردوش-غالاي ، يمكن حل المسألة عن طريق اختبار صحة${\displaystyle n}$عدم المساواة. ^{[ 4 ]}

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

تُشابه هذه المسائل مسائلَ تتابعات درجات الرسوم البيانية الثنائية البسيطة أو تتابعات درجات الرسوم البيانية الموجهة البسيطة . تُعرف المسألة الأولى بمسألة تحقيق الرسوم البيانية الثنائية ، بينما تُعرف الثانية بمسألة تحقيق الرسوم البيانية الموجهة .

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