المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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

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

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

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

المعطيات
مخطط موجه أو عادي، وقمتين 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
Nuvola apps edu mathematics-ar.svg
هذه بذرة مقالة عن الرياضيات بحاجة للتوسيع. شارك في تحريرها.