Question

max_flow
min_cut

הצע אלגוריתם אשר בהינתן רשת זרימה N=(G,c,s,t)N = (G,c,s,t) עם קיבולים שלמים, מוצא חתך מינימום בעל מספר מינימלי של קשתות מבין כל חתכי המינימום ברשת.

רמז: הגדירו פונקציית קיבול חדשה.

1

Answers

נגדיר פונקציית קיבול חדשה c^(e)=c(e)+1m\hat{c}(e) = c(e) + \frac{1}{m}.

טענה: חתך מינימום לפי הקיבול החדש אמ"מ הוא חתך מינימום עם מספר קשתות מינימלי לפי הקיבול המקורי.

הוכחה: יהא SS חתך מינימום לפי cc עם מספר מינימלי של קשתות. נסמן ב-S|S|את מספר הקשתות שחוצות את SS ונניח בשלילה שקיים חתך SS' כך ש-c^(S)<c^(S)\hat{c}(S') < \hat{c}(S) אז מתקיים:

c(S)+Sm=c^(S)<c^(S)=c(S)+Sm c(S') + \frac{|S'|}{m} = \hat{c}(S') < \hat{c}(S) = c(S) + \frac{|S|}{m}

סתירה.

בכיוון השני, אם SS חתך מינימום לפי c^\hat{c}

נניח בשלילה שקיים חתך SS' כך ש-c(S)c(S)+1c(S') \leq c(S) + 1 אז מתקיים

c^(S)Sm=c(S)c(S)+1=c^(S)Sm+1 \hat{c}(S') - \frac{|S'|}{m} = c(S') \leq c(S) + 1 = \hat{c}(S) - \frac{|S|}{m} + 1

סתירה.

נניח בשלילה שקיים חתך SS' כך ש-c(S)=c(S),S<Sc(S') = c(S), |S'| < |S| אז מתקיים

c^(S)Sm=c(S)=c(S)=c^(S)Sm \hat{c}(S') - \frac{|S'|}{m} = c(S') = c(S) = \hat{c}(S) - \frac{|S|}{m}

סתירה.

1
Feedback