مسار هاملتونياني
في نظرية التعقيد وفي نظرية المخططات، تحديد مسار هاملتونياني هو أحد مسائل 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
مراجع
- Eric Weinstein، "Biconnected Graph"، Wolfram MathWorld، مؤرشف من الأصل في 15 يناير 2018.
- Gould, Ronald J. (8 يوليو 2002)، "Advances on the Hamiltonian Problem - A Survey" (PDF)، Emory University، مؤرشف من الأصل (PDF) في 13 يوليو 2018، اطلع عليه بتاريخ 10 ديسمبر 2012.
- 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.