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

تصغير|ثلاثة أمثلة على مسارات هاملتونية في مربع 8x8

في نظرية التعقيد وفي نظرية البيان، تحديد مسار هاملتوني هو أحد مسائل NP الكاملة.Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957  وهناك عدة نسخ لهذه المسألة من بينها:
 مسار هاملتون المغلق 
المعطيات مخطط موجه أو عادي.
المسألة هل يوجد بالمخطط مسار مغلق يمر بجميع الرؤوس مرة واحدة واحدة(توكيد لفظي وليس تكرار)؟
 مسار هاملتون المفتوح 
المعطيات مخطط موجه أو عادي، وقمتين S و T.
المسألة هل يوجد بالمخطط مسار مفتوح طرفاه S و T، يمر بجميع الرؤوس مرة واحدة واحدة(توكيد لفظي وليس تكرار)؟

 استخدامات 
يستخدم المسار الهاملتوني في حل المشكلات والأحجيات مثل أحجية ن.

 بيبليوغرافيا 
  Leonard Adleman, "An Abstract Theory of Computer Viruses", Springer-Verlag New York, Inc., 1990, ISBN 0-387-97196-3
  Leonard Adleman, "Towards a (MATH)ematical theory of self-assembly. Technical Report 00-722", Department of Computer Science, University of Southern California, 2000, ISBN 2-7011-4032-3
  Jean-Baptiste Waldner, "Nano-informatique et intelligence quantique - Inventer l'ordinateur du ", Hermes Science, London, 2006, ISBN 2-7462-1516-0

 مراجع 

تصنيف:مسائل كثيرة حدود غير قطعية كاملة
تصنيف:معضلات حاسوبية في نظرية البيان
تصنيف:وليم روان هاملتون