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

من موسوعة العلوم العربية
اذهب إلى التنقل اذهب إلى البحث
لم تعد النسخة القابلة للطباعة مدعومة وقد تحتوي على أخطاء في العرض. يرجى تحديث علامات متصفحك المرجعية واستخدام وظيفة الطباعة الافتراضية في متصفحك بدلا منها.

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

مسار هاملتون المغلق

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

مسار هاملتون المفتوح

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

بيبليوغرافيا

  • قالب:En Leonard Adleman, "An Abstract Theory of Computer Viruses", Springer-Verlag New York, Inc., 1990, ISBN 0-387-97196-3
  • قالب:En 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
  • قالب:Fr Jean-Baptiste Waldner, "Nano-informatique et intelligence quantique - Inventer l'ordinateur du قالب:S-", Hermes Science, London, 2006, ISBN 2-7462-1516-0


ca:Camí hamiltonià cs:Hamiltonovský graf da:Hamiltonkreds de:Hamiltonkreisproblem en:Hamiltonian path es:Camino hamiltoniano fa:مسیر همیلتونی fi:Hamiltonin polku fr:Graphe hamiltonien he:מסלול המילטוני hu:Hamilton-út it:Cammino hamiltoniano ja:ハミルトン路 ko:해밀턴 경로 lt:Hamiltono maršrutas nl:Hamiltonpad pl:Graf hamiltonowski pms:Graf hamiltonian pt:Caminho hamiltoniano ru:Гамильтонов граф sk:Hamiltonovská kružnica sl:Hamiltonova pot sr:Хамилтонов пут sv:Hamiltongraf uk:Гамільтонів граф ur:ہملٹونین مخطط vi:Đường đi Hamilton zh:哈密顿图