مسار هاملتوني
مسألة 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