Question

min_cut
max_flow

תהא N=(G,c,s,t)N = (G, c, s, t) רשת זרימה.

  • קשת eEe \in E תקרא קשת קריטית מלמעלה אם לכל ε>0\varepsilon > 0, הגדלת c(e)c(e) ב-ε\varepsilon תגרום להגדלת ערך זרימת המקסימום ב-NN.
  • קשת eEe \in E תקרא קשת קריטית מלמטה אם לכל ε>0\varepsilon > 0, הקטנת c(e)c(e) ב-ε\varepsilon תגרום להקטנת ערך זרימת המקסימום ב-NN.
  1. הציעו אלגוריתם יעיל ככל האפשר המוצא את כל הקשתות הקריטיות מלמעלה.
  2. הציעו אלגוריתם יעיל ככל האפשר המוצא את כל הקשתות הקריטיות מלמטה.
1

Answers

1. טענה: (נובע ישירות ממשפט זרימת מקסימום) קשת ee היא קריטית מלמעלה אמ"מ ב-Gf{e}G_{f^*} \cup \{e\}, עבור ff^* זרימת מקסימום כלשהי, קיים מסלול stst.

אלגוריתם:

  • מצא זרימת מקסימום, ff^*, וחשב את GfG_{f^*}.
  • עבור כל קשת, ee, קבע שהיא קריטית מלמעלה אמ"מ ב-Gf{e}G_{f^*} \cup \{e\} קיים מסלול stst.

נכונות: מידית מהטענה.

סיבוכיות:

  • מציאת זרימת מקסימום ב-O(VE2)O(VE^2).
  • בדיקת קיום מסלול עבור קשת בודדת ניתן לעשות בזמן לינארי ועבור כל הקשתות ב-O(VE+E2)O(VE + E^2).
  • סך הכל O(VE2)O(VE^2).

2. טענה: (נובע ישירות ממשפט זרימת מקסימום) קשת ee היא קשת קריטית מלמטה אמ"מ קיים חתך-st מינימום, SS, כך ש-eδ(S)e \in \delta(S).

טענה: קיים חתך-st מינימום כך שהקשת uvδ(S)uv \in \delta(S) אמ"מ בגרף השיורי GfG_{f^*}, עבור זרימת מקסימום ff^*, כלשהי, לא קיים מסלול utu \rightsquigarrow t וגם לא קיים מסלול uvu \rightsquigarrow v.

הוכחה: אם לא קיימים מסלולים כנ"ל אז נסתכל על קבוצת הצמתים, SS, שישיגים מ-{s,u}\{s,u\} ב-GfG_{f^*}. קל לוודא ש-SS הוא חתך-st מינימום ב-GG.

מצד שני, נניח בשלילה שקיים חתך-st מינימום, SS, שמכיל את uu ולא מכיל את vv, מכיוון שקיים מסלול מ-uu ל-vv או ל-tt בגרף השיורי אז קיימת קשת abab בגרף השיורי שחוצה את SS וזה קורה אמ"מ f(ab)<c(ab)f(ab) < c(ab) או f(ba)>0f(ba) > 0 ובכל מקרה זה אינו חתך מינימום.

אלגוריתם:

  • חשב זרימת מקסימום, ff^* ואת הגרף השיורי GfG_{f^*}.
  • לכל צומת חשב את קבוצת הצמתים הישיגים ממנו.
  • החזר את קבוצת הקשתות uvuv כך ש-vv ו-tt אינם ישיגים מ-uu.

נכונות: מידית מהטענות.

סיבוכיות:

  • חישוב זרימת מקסימום וגרף שיורי O(VE2)O(VE^2).
  • מציאת צמתים ישיגים לצומת בודד אפשר לעשות בזמן לינארי ובסך הכל ב-O(V2+VE)O(V^2 + VE).
  • בסך הכל O(VE2)O(VE^2).
1
Feedback