Question

dynamic_programming
scc

יהא G=(V,E)G = (V, E) גרף מכוון ותהא L:VRL:V \to \mathbb{R} פונקציה המתאימה לכל צומת מספר ממשי. לכל צומת vVv \in V נסמן ב-R(v)R(v) את קבוצת הצמתים אליהם יש מסלול מכוון מ-vv ונגדיר l(v)=minwR(v)L(w)l(v) = \displaystyle{\min_{w \in R(v)}} L(w).

  1. הציעו אלגוריתם שמחשב את l(v)l(v) לכל צומת vVv \in V כאשר GG חסר מעגלים.
  2. הציעו אלגוריתם שמחשב את l(v)l(v) לכל צומת vVv \in V כאשר GG גרף כללי.
1

Answers

1. נשים לב שלפי ההגדרה של l(v)l(v) נובע ש:

l(v)=min{L(v),minvwEl(w)} l(v) = \min \{L(v), \min_{vw \in E} l(w)\}

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

2. נשים לב שבגרף כללי מתקיים ש-R(v)=R(u)R(v) = R(u) אמ"מ uu ו-vv נמצאים באותו רק"ה, ולכן ניתן לחשב את ll עבור גרף הרק"ה של GG בזמן לינארי.

1
Feedback