בעיית המסלול הארוך ביותר

		יש לשכתב ערך זה. הסיבה לכך היא: נוסח שאינו מובן כלל למי שאינו מתמצא בנושא.
		אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.	עריכה

בתורת הגרפים, בעיית המסלול הארוך ביותר זו הבעיה של מציאת המסלול הפשוט עם המשקל/אורך המקסימלי בגרף נתון. גרף נקרא פשוט אם הוא עובר בכל קודקוד במסלול פעם אחת בלבד. בניגוד לבעיית המסלול הקצר בגרף, אשר שואלת מה הדרך הקצרה ביותר בין שני קודקודים ויכולה להיפתר בזמן פולינומיאלי כל עוד אין מעגלים שלילים, בעיית המסלול הארוך היא בעיית NP שלמה, כלומר אי אפשר למצוא את הפתרון האופטימלי בזמן פולינומיאלי.

הרדוקציה

1. להראות שהבעיה היא ב-NP: בהינתן מסלול בגרף ניתן לבדוק אם הוא מקסימלי או לא. אם אפשר להוסיף עוד קודקוד עם משקל חיובי למסלול אז הוא לא, אם אין אפשרות להוסיף עוד קודקוד אז הוא מקסימלי
2. לבחור בעיה מוכרת ב-NPC: במקרה זה נבחר את מסלול המילטוני כבעיה המוכרת
3. לתאר טרנספורמציה שתיקח כל מופע של הבעיה המוכרת ותהפוך אותו למופע של הבעיה החדשה. הטרנספורמציה: ניקח את הגרף ונגדיר משקל כל צלע להיות שווה ל 1 ונשאל האם משקל המסלול הארוך ביותר שווה למספר הקודקודים בגרף =v
4. להוכיח שהתשובה היא כן לבעיה אם ורק אם התשובה היא כן גם לבעיה המוכרת
   1. צד 1 - אם יש מסלול המילטוני מכאן שיש מסלול שעובר בכל הקודקודים בגרף פעם אחת בדיוק כלומר למסלול יש V קודקודים וצלעות. בגלל שמשקל כול צלע הוא 1 אז משקל המסלול הוא V ולכן התשובה חיובית גם לבעיה החדשה
   2. צד 2 - אם יש מסלול באורך V בגרף כלומר המסלול עובר ב V קודקודים אבל V הוא מספר הקודקודים בגרף ולכן יש גם מסלול המילטוני
5. להראות שאפשר לבצע את הטרנספורמציה בזמן ליניארי: מכיוון שאנחנו לא משנים את הגרף רק סופרים את מספר הקודקודים בו לכל היותר יקח לנו V בשביל לעבור על כל הקודקוים לכן הטרנספורמציה היא ליניארית