בשאלה זו נעסוק בבעיות מעגל ומסלול המילטון בגרפים מכוונים ולא מכוונים. 1. נציע את הרדוקציה הבאה מן הבעיה DHC לב…

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

1. נציע את הרדוקציה הבאה מן הבעיה $DHC$ לבעיה $UHC$. בהינתן גרף מכוון $G=(V,E)$ נבנה גרף לא מכוון $G'=(V',E')$ כך:

   • לכל קודקוד $v\in V$ יהיו ב-$V'$ שלושה קודקודים $v_{in},v_{mid},v_{out}$.
   • לכל $v\in V$ יהיו ב-$E'$ שתי הקשתות הלא מכוונות $$\{v_{in},v_{mid}\},\ \{v_{mid},v_{out}\}.$$
   • לכל קשת מכוונת $(u,v)\in E$ תהיה ב-$E'$ הקשת הלא מכוונת $$\{u_{out},v_{in}\}.$$

   הוכיחו כי האלגוריתם הוא רדוקציית זמן פולינומי מ-$DHC$ ל-$UHC$.

   המלצה: שרטטו מספר גרפים מכוונים פשוטים וראו כיצד האלגוריתם עובד.

2. הוכיחו כי הבעיות $DHP,DHC,UHC,UHP$ שקולות פולינומית, והסיקו שכולן $NP$-קשות.

   הדרכה: מספיק להראות כי

   $$DHP\le_p DHC\le_p UHC\le_p UHP\le_p DHP.$$

   הסבירו מדוע זה מספיק.