נסמן ב-DHP את בעיית המסלול ההמילטוני בגרפים מכוונים, ב-UHP את הבעיה בגרפים לא מכוונים, ב-DHC את בעיית המעגל הה…

נסמן ב-$DHP$ את בעיית המסלול ההמילטוני בגרפים מכוונים, ב-$UHP$ את הבעיה בגרפים לא מכוונים, ב-$DHC$ את בעיית המעגל ההמילטוני בגרפים מכוונים וב-$UHC$ את הבעיה בגרפים לא מכוונים. בשיעור צוין ללא הוכחה כי כולן $NP$-קשות.

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

   $$V'=\{v_{in}:v\in V\}\cup\{v_{mid}:v\in V\}\cup\{v_{out}:v\in V\},$$ $$E'=\{v_{in}v_{mid}:v\in V\}\cup\{v_{mid}v_{out}:v\in V\}\cup\{u_{out}v_{in}:uv\in E\}.$$

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

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

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

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

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

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