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=S1S2S = S_1 \cup S_2 תהא ff זרימת מקסימום ותהא קשת uvuv כך ש-uSu \in S ו-v/Sv \notin S. נניח בלי הגבלת הכלליות ש-uS1u \in S_1 אז מכיוון ש-S1S_1 חתך מינימום מתקיים ש-f(uv)=c(uv)f(uv) = c(uv). כעת נסמן S=S1S2S = S_1 \cap S_2 ונסתכל על קשת uvuv כך ש-uSu \in Sו-v/Sv \notin S. נניח בלי הגבלת הכלליות ש-v/S1v \notin S_1 אז מכיוון ש-S1S_1 חתך מינימום מתקיים ש-f(uv)=c(uv)f(uv) = c(uv).

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

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

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

2
Feedback