دورة هاميلتون، التحقق والإيجاد

Question

إذا كان لدينا خوارزمية في وقت متعدد الحدود يقول إذا كان الرسم البياني G لديه دورة Hamiltonian، هل يمكن أن يكون لدينا خوارزمية في وقت متعدد الحدود العثور على دورة Hamiltonian؟

محاولتي هي حذف حافة الرسم البياني G وتناول G '، بعد تشغيل الخوارزمية على G' لمعرفة ما إذا كان لها دورة هاميلتون إذا لم يكن الأمر كذلك يعني أن الحافة في بعض دورة هاميلتون.الآن أنا لا أعرف كيفية الذهاب.

Answer 1

دع $ P $ يكون مسارا بسيطا بسيطا في الرسم البياني. إذا ظهرت $ P $ في دورة Hamiltonian من الرسم البياني، يمكنك إزالة جميع رؤوس $ P $ باستثناء قمة الأولى والأخيرة، قم بتوصيل هاتين الرأسين بحافة ورسم الرسم البياني الناتج هو هاميلتون.

مع مراعاة ذلك، يمكننا بناء دورة هاميلتون خطوة بخطوة تبدأ بمسار طول واحد، لأنك وصفت بالفعل كيفية بناء هذا المسار. ثم يمكننا تمديد مسار طول $ I $ إلى مسار طول $ i + 1 $ استخدام الخدعة أعلاه، حيث نحاول جميع جيران جميع جيران آخر قمة في المسار كأداة قسمة واحدة وقمنا بتطبيق الحيلة أعلاه للتحقق مما إذا كانت دورة Hamiltonian موجودة حيث يكون المسار الجديد جزءا من الدورة. لاحظ أننا نسمي المربع الأسود على معظم $ M:= | E | $ Times. بمجرد أن نصل إلى مسار طول $ n-3 $ من السهل إكمال المسار في دورة هاميلتون في الوقت الخطي.