מפת הסיבוכיות
EN
שלישיית $v_{in},v_{mid},v_{out}$ לכל קודקוד

DHC ≤p UHC

DHC≤pUHCDHC\le_p UHC — מעגל המילטוני בגרף מכוון ניתן לרדוקציה למעגל המילטוני בגרף לא מכוון, על ידי קידוד הכיווניות בתוך מבנה הגרף.

הבנייה

בהינתן גרף מכוון G=(V,E)G=(V,E) נבנה גרף לא מכוון G′=(V′,E′)G'=(V',E'):

V′={vin:v∈V}∪{vmid:v∈V}∪{vout:v∈V},V'=\{v_{in}:v\in V\}\cup\{v_{mid}:v\in V\}\cup\{v_{out}:v\in V\}, E′={vinvmid:v∈V} ∪ {vmidvout:v∈V} ∪ {uoutvin:uv∈E}.E'=\{v_{in}v_{mid}:v\in V\}\ \cup\ \{v_{mid}v_{out}:v\in V\}\ \cup\ \{u_{out}v_{in}:uv\in E\}.

כלומר כל קודקוד מוחלף במסלול באורך שתיים vin−vmid−voutv_{in}-v_{mid}-v_{out}, וכל קשת מכוונת u→vu\to v הופכת לקשת לא מכוונת מהיציאה של uu אל הכניסה של vv.

מה מקודד את הכיווניות. הקודקוד vmidv_{mid} הוא בעל דרגה 22 בדיוק — שכניו היחידים הם vinv_{in} ו-voutv_{out}. מעגל המילטוני חייב לעבור בכל קודקוד, ובקודקוד מדרגה 22 הוא חייב להשתמש בשתי קשתותיו. לכן כל מעגל המילטוני ב-G′G' חוצה כל שלישייה במסלול vin→vmid→voutv_{in}\to v_{mid}\to v_{out} או בהיפוכו — ומכיוון שהמעגל אחד, הבחירה אחידה לכל השלישיות. זו בדיוק הכיווניות שאבדה כשעברנו לגרף לא מכוון.

המחשה

בנייה מודרכת

מעגל המילטוני מכוון → לא מכוון

שלב 1 מתוך 7
מעגל המילטוני מכוון ברדוקציה למעגל המילטוני לא מכווןמשמאל גרף מכוון על ארבעה קודקודים; מימין כל קודקוד מורחב לשלישייה in, mid, out המסודרת סביב מעגל, כך שהמעגל ההמילטוני עובר על הטבעת וקודקודי האמצע מדרגה שתיים כופים כיוון אחיד.G — מכוון1→22→33→44→13→11234G′ — לא מכווןכל קודקוד עומד להפוך לשלישייה

נכונות — שני הכיוונים

DHC ∈ ⟹ UHC ∈

נניח G∈DHCG\in DHC; קיים ב-GG מעגל המילטוני מכוון v(1)→v(2)→⋯→v(n)→v(1)v^{(1)}\to v^{(2)}\to\dots\to v^{(n)}\to v^{(1)}.

נבנה ב-G′G' את המעגל vin(1)→vmid(1)→vout(1)→vin(2)→vmid(2)→vout(2)→⋯→vout(n)→vin(1).v^{(1)}_{in}\to v^{(1)}_{mid}\to v^{(1)}_{out}\to v^{(2)}_{in}\to v^{(2)}_{mid}\to v^{(2)}_{out}\to\dots\to v^{(n)}_{out}\to v^{(1)}_{in}.

כל הקשתות קיימות: הקשתות vinvmidv_{in}v_{mid} ו-vmidvoutv_{mid}v_{out} קיימות לכל vv לפי הבנייה; והקשת vout(t)vin(t+1)v^{(t)}_{out}v^{(t+1)}_{in} קיימת מפני ש-v(t)v(t+1)v^{(t)}v^{(t+1)} היא קשת מכוונת של GG (היא קשת של המעגל).

המעגל המילטוני: הוא עובר בכל vin,vmid,voutv_{in},v_{mid},v_{out} עבור כל v∈Vv\in V בדיוק פעם אחת, שכן המעגל המקורי עובר בכל vv בדיוק פעם אחת. לכן הוא מכסה את כל ∣V′∣=3∣V∣|V'|=3|V| הקודקודים. לכן G′∈UHCG'\in UHC.

UHC ∈ ⟹ DHC ∈

נניח G′∈UHCG'\in UHC, ויהי C′C' מעגל המילטוני ב-G′G'.

צעד 1 — השלישיות נחצות ברצף. יהי v∈Vv\in V. הקודקוד vmidv_{mid} בעל דרגה 22 ב-G′G': שכניו היחידים הם vinv_{in} ו-voutv_{out} (הבנייה אינה מוסיפה לו שום קשת אחרת). מעגל המילטוני עובר ב-vmidv_{mid} ומשתמש בדיוק בשתי קשתות הנוגעות בו, ומכיוון שיש רק שתיים — הוא משתמש בשתיהן. לכן ב-C′C' מופיע הקטע vin−vmid−voutv_{in}-v_{mid}-v_{out} (באחד משני הכיוונים), ובפרט vinv_{in} ו-voutv_{out} אינם שכנים זה של זה ב-C′C' דרך מסלול אחר.

צעד 2 — הכיוון אחיד. נבחר כיוון מעבר על C′C'. לפי צעד 1, בכל שלישייה C′C' נכנס דרך vinv_{in} ויוצא דרך voutv_{out}, או להפך. נניח בלי הגבלת הכלליות (על ידי היפוך כיוון המעבר על C′C') שקיימת שלישייה שבה נכנסים ב-vinv_{in}. נראה שכך בכולן: הקשת שאחרי voutv_{out} ב-C′C' אינה קשת פנימית של השלישייה, ולכן היא מהצורה voutuinv_{out}u_{in} — הקשתות היחידות היוצאות מקודקוד outout הן לקודקודי inin. לכן השלישייה הבאה נכנסת אף היא ב-uinu_{in}. באינדוקציה לאורך המעגל, כל השלישיות נחצות בכיוון in→mid→outin\to mid\to out.

צעד 3 — קריאת המעגל המכוון. נסמן ב-v(1),v(2),…,v(n)v^{(1)},v^{(2)},\dots,v^{(n)} את סדר השלישיות לאורך C′C'. לפי צעד 2, בין השלישייה של v(t)v^{(t)} לשלישייה של v(t+1)v^{(t+1)} מופיעה ב-C′C' הקשת vout(t)vin(t+1)v^{(t)}_{out}v^{(t+1)}_{in}. הקשתות מסוג זה קיימות אך ורק כאשר v(t)v(t+1)∈Ev^{(t)}v^{(t+1)}\in E — כך הוגדר E′E'. לכן v(t)→v(t+1)v^{(t)}\to v^{(t+1)} היא קשת מכוונת של GG לכל tt, וכן v(n)→v(1)v^{(n)}\to v^{(1)} (הקשת הסוגרת).

מכיוון ש-C′C' המילטוני ב-G′G', כל שלישייה מופיעה בו בדיוק פעם אחת, ולכן v(1),…,v(n)v^{(1)},\dots,v^{(n)} הם כל קודקודי VV כל אחד פעם אחת. לכן v(1)→⋯→v(n)→v(1)v^{(1)}\to\dots\to v^{(n)}\to v^{(1)} הוא מעגל המילטוני מכוון ב-GG, כלומר G∈DHCG\in DHC.

סיבוכיות הרדוקציה

זמןO(|V| + |E|)
מקוםO(|V| + |E|)
גודל הפלט3|V| vertices, 2|V| + |E| edges

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

מה זה קונה

חוליה במעגל DHP≤pDHC≤pUHC≤pUHP≤pDHPDHP\le_p DHC\le_p UHC\le_p UHP\le_p DHP, שמראה שארבע הבעיות ההמילטוניות שקולות פולינומית, ולכן אם אחת מהן NP-קשה — כולן.

מלכודות

  • vmidv_{mid} אינו קישוט. בלעדיו vinv_{in} ו-voutv_{out} היו מחוברים בקשת אחת, והמעגל היה יכול לחצות שלישייה "לרוחב" בלי לכפות סדר. הדרגה 22 של vmidv_{mid} היא כל מנגנון הכפייה.

  • אחידות הכיוון דורשת הוכחה. לא מספיק לומר "כל שלישייה נחצית בכיוון כלשהו" — צריך את הטיעון שקשת יוצאת מ-outout מגיעה תמיד ל-inin, ולכן הכיוון מתפשט לאורך כל המעגל. בלי צעד 2 אין דרך לקרוא מעגל מכוון מהמעגל הלא מכוון.

השרשרת

משמשת בהמשך ל

מאיפה זה נקרא

  • 2026"הוכיחו כי האלגוריתם הוא רדוקציית זמן פולינומי מ-DHCDHC ל-UHCUHC" — הבנייה ניתנת במלואה בגוף השאלה.
  • 2026אותה בנייה, בניסוח קבוצתי של V′V' ו-E′E'.

  • שיעור 12 מוסר את ארבע הרדוקציות של המעגל ההמילטוני כתרגילי בית ואינו כותב אף אחת מהן; מה שנכתב בשיעור הוא רק טיעון הטרנזיטיביות (מדוע די ב-4 רדוקציות במקום 12). הבנייה שלמעלה מועתקת מהניסוח שהבחינות של 2026 נותנות לה.