Question

max_flow
min_cut

יהא G=(V,E)G = (V,E) גרף מכוון, ויהיו U1,U2VU_1, U_2 \subset V שתי קבוצות צמתים זרות.

הציעו אלגוריתם שמחשב את מספר הקשתות המינימלי שיש להסיר מהגרף, כך שלא יהיה שום מסלול מצומת ב-U1U_1 לצומת ב-U2U_2.

1

Answers

נרצה למצוא חתך מינימלי שמכיל את כל צמתי U1U_1 ולא מכיל אף צומת מ-U2U_2. כדי לעשות זאת נבנה רשת זרימה על ידי הוספת צומת מקור, ss, שנחבר לכל צמתי U1U_1 עם קשתות בעלות קיבול אינסופי, ובנוסף צומת יעד, tt, שנחבר אליה את כל צמתי U2U_2 עם קשתות בעלות קיבול אינסופי. לקשתות הגרף המקורי ניתן קיבול 1. קל לראות שכל חתך stst עם קיבול סופי מכיל את כל צמתי U1U_1 ולא מכיל אף צומת מ-U2U_2.

טענה: מספר הקשתות שחוצות חתך stst מינימלי ברשת הזרימה הנ"ל, kk הוא מספר הקשתות המינימלי שיש להסיר על מנת שלא יהיה מסלול מצומת ב-U1U_1 לצומת ב-U2U_2.

הוכחה: קל לראות שאם מסירים את כל הקשתות שחוצות חתך stst מינימלי אז לא קיים מסלול מצומת ב-U1U_1 לצומת ב-U2U_2. מצד שני, נניח בשלילה שניתן להסיר מספר קטן יותר של קשתות, l<kl < k כך שלא יהיה קיים מסלול כנ"ל, נסיר אותן ונסתכל על החתך שמוגר על ידי כל הצמתים שישיגים מ-ss, את החתך הזה לא חוצה אף קשת ולפני שהסרנו את הקשתות חצו אותו לכל היותר l<kl < k קשתות - סתירה.

אלגוריתם:

  • בנה את הרשת הנ"ל
  • מצא חתך מינימום והחזר אותו

נכונות: נובעת מהדיון לעיל.

סיבוכיות: ניתן לחשב חתך מינימום (זרימת מקסימום) בזמן (k(E+V))(k(E + V)) כאשר kk מספר הקשתות המינימלי שיש להסיר מהגרף.

1
Feedback