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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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

مسار هاملتون المغلق[عدل]

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

مسار هاملتون المفتوح[عدل]

المعطيات
مخطط موجه أو عادي، وقمتين 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 XXIe قرن", Hermes Science, London, 2006, ISBN 2-7462-1516-0

مراجع[عدل]

  1. ^ Eric Weinstein. "Biconnected Graph". Wolfram MathWorld. 
  2. ^ Gould، Ronald J. (July 8, 2002). "Advances on the Hamiltonian Problem - A Survey" (PDF). Emory University. اطلع عليه بتاريخ 2012-12-10. 
  3. ^ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957


Nuvola apps edu mathematics-ar.svg
هذه بذرة مقالة عن الرياضيات بحاجة للتوسيع. شارك في تحريرها.