الرئيسيةبحث

مسار هاملتونياني

مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

في نظرية التعقيد و في نظرية المخططات، تحديد مسار هاملتونياني هو أحد مسائل NP الكاملة. و هناك عدة نسخ لهذه المسألة من بينها:

مسار هاملتون المغلق

المعطيات
مخطط موجه أو عادي.
المسألة
هل يوجد بالمخطط مسار مغلق يمر بجميع الرؤوس مرة واحدة واحدة(توكيد لفظي و ليس تكرار)؟

مسار هاملتون المفتوح

المعطيات
مخطط موجه أو عادي، و قمتين S و T.
المسألة
هل يوجد بالمخطط مسار مفتوح طرفاه S و T، يمر بجميع الرؤوس مرة واحدة واحدة(توكيد لفظي و ليس تكرار)؟

بيبليوغرافيا