مشكلة الدورة ذات الوزن الصفري

في علوم الحاسوب ونظرية الرسم البياني ، تُعرف مشكلة الدورة ذات الوزن الصفري بأنها مشكلة تحديد ما إذا كان الرسم البياني الموجه ذو الأوزان على الحواف (والتي قد تكون موجبة أو سالبة أو صفرية) يحتوي على دورة يكون فيها مجموع الأوزان  0.

تتمثل إحدى المشكلات ذات الصلة في تحديد ما إذا كان الرسم البياني يحتوي على دورة سالبة، وهي دورة يكون فيها مجموع الأوزان أقل من الصفر. يمكن حل هذه المشكلة في وقت متعدد الحدود باستخدام خوارزمية بيلمان-فورد . إذا لم تكن هناك دورة سالبة، فيمكن استخدام المسافات التي تم إيجادها بواسطة خوارزمية بيلمان-فورد، كما هو الحال في خوارزمية جونسون ، لإعادة ترجيح حواف الرسم البياني بحيث تصبح جميع أوزان الحواف غير سالبة وتبقى جميع أطوال الدورات دون تغيير. مع إعادة الترجيح هذه، يصبح اكتشاف دورة ذات وزن صفري أمرًا بسيطًا: فهي موجودة إذا وفقط إذا لم تُشكّل الحواف ذات الوزن الصفري رسمًا بيانيًا موجهًا غير دوري . لذلك، فإن الحالة الخاصة لمشكلة الدورة ذات الوزن الصفري، على الرسوم البيانية التي لا تحتوي على دورة سالبة، لها خوارزمية تعمل في وقت متعدد الحدود . ^{[ 1 ]}

في المقابل، بالنسبة للرسوم البيانية التي تحتوي على دورات سالبة، يُعدّ اكتشاف دورة بسيطة وزنها صفرًا بالضبط مشكلةً كاملةً من فئة NP . ^{[ 1 ]} هذا صحيح حتى عندما تكون الأوزان أعدادًا صحيحة ذات قيمة متعددة الحدود. على وجه الخصوص، يوجد اختزال من مشكلة مسار هاميلتوني ، على${\displaystyle n}$رسم بياني غير مرجح ذو رؤوس${\displaystyle G}$مع رؤوس بداية ونهاية محددة${\displaystyle s}$و${\displaystyle t}$، إلى مسألة الدورة ذات الوزن الصفري على الرسم البياني الموزون الذي تم الحصول عليه عن طريق إعطاء جميع حواف${\displaystyle G}$وزن يساوي واحدًا، وإضافة حافة إضافية من${\displaystyle t}$ل${\displaystyle s}$مع الوزن${\displaystyle 1-n}$[ ^{2 ]​}