مسار هاملتونياني
اذهب إلى التنقل
اذهب إلى البحث
قالب:مسألة 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:哈密顿图