Question

winter_09-10_b
dynamic_programming
mst

יהא G=(V,E)G = (V, E) גרף לא מכוון עם פונקציית משקל על קשתותיו, ויהא TT עץ פורש (לאו דווקא מינימום) של GG. לכל זוג צמתים u,vVu, v \in V נסמן ב-Pu,vP_{u,v} את המסלול היחיד ב-TT המחבר אותם, ונסמן ב-Wu,vW_{u,v} את משקל הקשת הכבדה ביותר ב-Pu,vP_{u,v}.

א. הציעו אלגוריתם המחשב את Wu,vW_{u,v} לכל u,vVu,v \in V. על האלגוריתם לרוץ בזמן O(V2)O(V^2). הוכיחו נכונות ונתחו סיבוכיות.

ב. הציעו אלגוריתם המוצא את כל הקשתות בגרף שאינן מופיעות באף עץ פורש מינימום.

על האלגוריתם לרוץ בזמן O(V2+ElogV)O(V^2 + E\log V). הוכיחו נכונות ונתחו סיבוכיות.

1

Answers

א. נקבע צומת uu, ונשים לב שמתקיים

Wu,v=max{w(u,p(v)),Wu,p(v)} W_{u, v} = \max \{w(u, p(v)), W_{u, p(v)}\}

כאשר p(v)p(v) הוא האבא של vv ביחס לשורש uu. תנאי הקצה הוא Wu,u=0W_{u, u} = 0.

ניתן לחשב את הערכים הנ"ל עבור כל הצמתים על ידי תכנון דינאמי בזמן O(V)O(V) ניתן לחזור על החישוב הנ"ל עבור כל צומת ובסך הכל בזמן O(V2)O(V^2) לחשב את הערך המתאים לכל זוג צמתים.

ב.

אלגוריתם:

  • מצא עפ"מ TT וחשב Wu,vW_u,v ביחס ל-TT עבור כל u,vVu,v \in V.
  • החזר {uvET:Wu,v<w(uv)}\{uv \in E \setminus T : W_{u, v} < w(uv)\}

סיבוכיות:

  • מציאת עפ"מ בזמן O(ElogV)O(E\log V)
  • חישוב Wu,vW_{u,v} ואת פלט האלגוריתם ניתן לעשות בזמן O(V2)O(V^2).

נכונות: אם Wu,vw(uv)W_{u, v} \geq w(uv) אז ניתן להוסיף את uvuv ל-TT ולהוריד את הקשת הכבדה ביותר במעגל (במשקל Wu,vW_{u, v} ולקבל עפ"מ.

אם Wu,v<w(uv)W_{u, v} < w(uv) אז נשים לב שבכל חתך שקשת uvuv חוצה קיימת קשת קלה יותר שחוצה את אותו חתך (מהמעגל שנוצר כאשר מוסיפים את uvuv ל-TT) ולכן על פי משפט האפיון של עצים פורשים מינימום קשת זו אינה שייכת לאף עפ"מ.

1

Another approach for part 1, without dynamic programming :

Let us suggest an algorithm which finds wu,vw_{u,v} for all uVu\in V and specific vv which works in O(v)O(v) then we shall run it V|V| times (for each vVv\in V).

Algorithm:

  1. Pick a sVs\in V , define: ws,s=0w_{s,s} = 0.
  2. Run a BFS scan from ss.
  3. Go through the BFS layers (ds(v))d_s(v)) in increasing order and calculate wv,s=max{w(v,v.parent),w(v.parent,s)}w_{v,s} = max\{w(v,v.parent) ,w(v.parent, s)\}.

complexity:

  1. BFS takes P(V+E)P(V+E) when for TT, ET=V1|E_T| = |V|-1, so O(E+V)=O(V)O(E+V) = O(V).
  2. iterating through every layer takes O(V)O(V) and for every vv the calculation is made in O(1)O(1).

So for all pairs, one may run the last algorithm for all vVv\in V which takes O(V2)O(V^2).

0
Feedback