Donate Home Top Contributors Back to Course
Log In Sign Up

Question

min_cut
max_flow

תהא N=(G,c,s,t)N = (G, c, s, t) רשת זרימה. נסמן ב-σ(N)\sigma(N) את קבוצת חתכי המינימום של NN.

  1. הוכיחו כי σ(N)\sigma(N) סגורה לאיחודים ולחיתוכים.
  2. נגדיר Smax⁡(N)=⋃S∈σ(N)SS_{\max}(N) = \bigcup_{S \in \sigma(N)}S ו-Smin⁡(N)=⋂S∈σ(N)SS_{\min}(N) = \bigcap_{S \in \sigma(N)}S הציעו אלגוריתם שמוצא את Smin⁡(N)S_{\min}(N) ואת Smax⁡(N)S_{\max}(N).
  3. הציעו אלגוריתם המכריע האם ברשת זרימה קיים חתך מינימום יחיד.
1

Answers

נזכיר שחתך הוא חתך מינימום אמ"מ בזרימת מקסימום כל הקשתות שחוצות את החתך רוויות.

1. יהיו S1S_1 ו-S2S_2 שני חתכי מינימום ו-S=S1∪S2S = S_1 \cup S_2 תהא ff זרימת מקסימום ותהא קשת uvuv כך ש-u∈Su \in S ו-v∈/ Sv \notin S. נניח בלי הגבלת הכלליות ש-u∈S1u \in S_1 אז מכיוון ש-S1S_1 חתך מינימום מתקיים ש-f(uv)=c(uv)f(uv) = c(uv). כעת נסמן S=S1∩S2S = S_1 \cap S_2 ונסתכל על קשת uvuv כך ש-u∈Su \in Sו-v∈/ Sv \notin S. נניח בלי הגבלת הכלליות ש-v∈/ S1v \notin S_1 אז מכיוון ש-S1S_1 חתך מינימום מתקיים ש-f(uv)=c(uv)f(uv) = c(uv).

2. (ללא הוכחה) כדי למצוא את Smin⁡S_{\min} נמצא זרימת מקסימום ונחזיר את קבוצת הצמתים שישיגים מ-ss ברשת השיורית. כדי למצוא את Smax⁡S_{\max} נמצא זרימת מקסימום ונחזיר את קבוצת הצמתים ש-tt אינו ישיג מהם.

3. נחזיר שקיים חתך יחיד אמ"מ Smin⁡=Smax⁡S_{\min} = S_{\max}.

נכונות: מיידית.

Discussion
avatar
2
Write Your Own Answer
Feedback