רדוקציה ממעגל המילטוני ל־TSP

המרת גרף למופע TSP מלא והוכחת שקילות הסף.

שאלה

בהינתן גרף לא־מכוון $G=(V,E)$ עם $n\ge3$, בנו גרף מלא ממושקל וסף $B$ כך של-$G$ יש מעגל המילטוני אם ורק אם קיים מסע TSP בעלות לכל היותר $B$. הוכיחו את שני הכיוונים, גודל פולינומי ושייכות ל-NP.

דרישות קדם

נדרשת שליטה בהגדרות היחידה ובניתוח אורכי קידוד. יש להבחין בין טענה מותנית, רדוקציה ואלגוריתם.

רמז 1

תנו עלות 1 לקשת מקורית ו-2 לקשת חסרה.

רמז 2

בכל מסע יש בדיוק $n$ קשתות.

רמז 3

המסע הוא תעודה פולינומית.

פתרון מלא

נבנה את הגרף המלא על $V$, נגדיר $c(u,v)=1$ אם $\{u,v\}\in E$ ו-$c(u,v)=2$ אחרת, ונבחר $B=n$. הפלט כולל $O(n^2)$ קשתות ועלויות בגודל קבוע ולכן הבנייה פולינומית.

אם ב-$G$ יש מעגל המילטוני, אותו סדר מחזורי משתמש ב-$n$ קשתות שעלות כל אחת 1, ולכן עלותו $n$. בכיוון ההפוך, כל מסע בגרף המלא מכיל בדיוק $n$ קשתות ועלות כל אחת לפחות 1. אם העלות לכל היותר $n$, כל הקשתות חייבות להיות בעלות 1, ולכן כולן שייכות ל-$E$. אותו סדר הוא מעגל המילטוני ב-$G$.

TSP ההכרעתי שייך ל-NP: תעודה היא תמורה של הקודקודים. המוודא בודק שכל קודקוד מופיע פעם אחת, מחבר את עלויות הקשתות כולל קשת החזרה ומשווה ל-$B$ באריתמטיקה בינארית פולינומית. יחד עם הרדוקציה מתקבלת NP-שלמות.

אין למחוק קשתות חסרות, כי מופע TSP מוגדר על גרף מלא; מענישים אותן בעלות 2. כמו כן זו רדוקציית הכרעה, לא הוכחת קירוב. אף שהעלויות 1 ו-2 מקיימות אי־שוויון משולש, פער האופטימום כאן אינו מעניק מעצמו יחס קירוב שימושי.

נקודות בדיקה

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

טעויות נפוצות

• השמטת קשת החזרה.
• אי־שימוש בחסם התחתון 1 לכל קשת.
• הסקת תוצאת קירוב מרדוקציית הכרעה.

מקורות ואימות

• 2026 transcript 14
• Sipser 3e, sec. 7.5
• Garey-Johnson, GT37 and ND22
• הערת כיסוי הקורפוס: אין כיסוי ישיר בסיכום הממוזג.
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

התרגיל הוא סינתזה מקורית. רמת הביטחון משקפת אימות של הטענה המתמטית מול מקורות ספרי הלימוד המפורטים לעיל; מקורות הקורס משמשים רק כאשר זוהה כיסוי ישיר.

פתיחה בגלריית ההמחשות: מעגל המילטוני → TSP