Question

matching
greedy
dynamic_programming

נתון עץ לא מכוון T=(V,E)T = (V, E). שידוך בגרף הוא קבוצת קשתות MEM \subseteq E, כך שכל צומת vv הוא קצה לכל היותר של קשת אחת בשידוך. לדוגמה, בעץ הבא הקשתות המקווקוות מהוות שידוך בגודל מקסימלי.

א. הציעו אלגוריתם חמדן הרץ בזמן O(V)O(V) המחשב שידוך בגודל מקסימלי בעץ TT.

ב. נתונה פונקציית משקל אי-שלילית על הקשתות w:ER+w:E \to \mathbb{R}^+. נגדיר משקל של שידוך בגרף להיות סכום משקלי הקשתות בשידוך. לדוגמה, בעץ הבא הקשתות המקווקוות מהוות שידוך במשקל מקסימלי:

הציעו אלגוריתם הרץ בזמן O(V)O(V) המחשב שידוך במשקל מקסימלי בעץ.

1

Answers

א. אלגוריתם:

  • הסר צמתים עם דרגה 0 מהגרף
  • אם אין צמתים בגרף החזר שידוך ריק
  • בחר צומת עם דרגה 1, uu, ושדך אותו לשכן שלו, vv.
  • המשך רקורסיבית על G[V{u,v}]G[V \setminus \{u, v\}]

סיבוכיות: ניתן לתחזק רשימות (תור) של צמתים עם דרגה 1 ו-0 ולתחזק אותן בכל פעם שמסירים צמתים מהגרף בזמן לינארי, ולכן סך הזמן הוא O(V+E)=O(V)O(V + E) = O(V).

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

בסיס: עבור עץ עם 0 צמתים האלגוריתם מוצא שידוך מקסימום.

צעד: נסמן את השידוך שמחזיר האלגוריתם ב-AA ונסתכל על שידוך מקסימום, MM עבור עץ (יער) עם nn צמתים. אםuvMuv \in M (הקשת שבוחר האלגוריתם) אז סיימנו. אחרת vv משודך לצומת ww ו-M=M{uv}{vw}M' = M \cup \{uv\} \setminus \{vw\} גם שידוך מקסימום. כמו כן M=M|M'| = |M| ביחס ל-G[V{u,v}]G[V \setminus \{u, v\}]

לפי הנחת האינדוקציה, AA שידוך מקסימום ביחס ל-G[V{u,v}]G[V \setminus \{u, v\}], ולכן A{uv}M=M|A \cup \{uv\}| \geq |M'| = |M|.

ב. נשריש את העץ בצורה שרירותית ונסמן ב-MvM_v את משקלו של שידוך במשקל מקסימלי עבור תת העץ ששורשו vv. כמו כן נסמן ב-MvM_{v}^- את משקלו של שידוך במשקל מקסימלי עבור תת העץ ששורשו vv כך שהצומת vv לא משודך.

קל לראות שעבור עץ, T=(V,E)T = (V, E) עם שורש rr מתקיים ש-

Mr=max{rvEMvmaxrvE  w(rv)+Mv+ruE:u̸=vMu M_r = \max \begin{cases} \displaystyle{\sum_{rv \in E}} M_v \\ \displaystyle{\max_{rv \in E}} \; w(rv) + M_v^- + \sum_{ru \in E : u \neq v} M_u \end{cases}

נשים לב שלכל צומת בעץ אנחנו שומרים שני ערכים וכי אפשר לחשב את הערכים האלו מהעלים של העץ כלפי מעלה כך שחישוב של ערך בודד נעשה בזמן לינארי במספר הבנים שלו, ולכן סך הכל ניתן לחשב את השידוך בזמן O(V)O(V).

1
Feedback