Question

max_flow
min_cut
proof

עבור גרף מכוון G=(V,E)G = (V, E) ושני צמתים s,vVs, v \in V נסמן ב-sGvs \underset{G}{\rightsquigarrow} v אם קיים מסלול מ-ss ל-vv ב-GG וב-s̸Gvs \underset{G}{\not\rightsquigarrow} v אם לא קיים מסלול כזה.

בהינתן רשת זרימה N=(G,c,s,t)N = (G, c, s, t) וזרימת מקסימום ff.

ראינו בהרצאה ש-S={v:sGfv}S = \{v : s \underset{G_f}{\rightsquigarrow} v \} הוא חתך מינימום ב-NN.

א. הוכיחו כי T={v:v̸Gft}T = \{v : v \underset{G_f}{\not\rightsquigarrow} t\} הוא חתך מינימום ב-NN.

ב. הוכיחו כי S=TS = T אמ"מ קיים חתך מינימום יחיד ב-NN.

1

Answers

א. נשים לב שב-GfG_f לא קיימת קשת שיוצאת מ-TT ל-VTV \setminus T ומכך ניתן להסיק כי כל הקשתות שיוצאות מ-TT ל-VTV \setminus T ב-GG רוויות ביחס ל-ff ועל כל הקשתות שנכנסות מ-VTV \setminus T ל-TT ב-GG יש זרימת 0 ולכן קיבול החתך שווה לזרימת המקסימום ff וזהו חתך מינימום.

ב. כיוון אחד טריוויאלי. נניח כי S=TS = T ונניח כי קיים חתך מינימום, S̸=SS' \neq S.

נחלק לשני מקרים:

  1. קיים צומת vSTv \in S' \setminus T אז מתקיים vtv \rightsquigarrow t ולכן ישנה קשת אחת לפחות שחוצה את SS' ב-GfG_f - סתירה.
  2. קיים צומת vSSv \in S \setminus S' אז מכיוון ש-sSs \in S' ו-svs \rightsquigarrow v אז קיימת קשת שחוצה את SS' ב-GfG_f - סתירה.
1
Feedback