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

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

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

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

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

  • (إنگليزية) Leonard Adleman, "An Abstract Theory of Computer Viruses", Springer-Verlag New York, Inc., 1990, ISBN 0387971963
  • (إنگليزية) Leonard Adleman, "Towards a (MATH)ematical theory of self-assembly. Technical Report 00-722", Department of Computer Science, University of Southern California, 2000, ISBN 2701140323
  • (بالفرنسية) Jean-Baptiste Waldner, "Nano-informatique et intelligence quantique - Inventer l'ordinateur du قالب:S-", Hermes Science, London, 2006, ISBN 2746215160