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

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

مسألة 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

مراجع
  1. Eric Weinstein. "Biconnected Graph". Wolfram MathWorld. مؤرشف من الأصل في 2018-01-15.
  2. Gould، Ronald J. (8 يوليو 2002). "Advances on the Hamiltonian Problem - A Survey" (PDF). Emory University. مؤرشف من الأصل (PDF) في 2018-07-13. اطلع عليه بتاريخ 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 نسخة محفوظة 22 أكتوبر 2016 على موقع واي باك مشين.
  • أيقونة بوابةبوابة رياضيات
  • أيقونة بوابةبوابة علم الحاسوب
  • أيقونة بوابةبوابة علم الفلك
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.