Question

max_flow
proof

בהינתן רשת זרימה, N=(G,s,t,c)N = (G, s, t, c), נאמר שזרימה f:ERf:E \to \mathbb{R} היא חסרת מעגלים אם לכל מעגל ברשת הזרימה יש לפחות קשת אחת שהזרימה עליה היא 0. כלומר, הקשתות בהן הזרימה חיוביות ממש משרות גרף חסר מעגלים.

הוכיחו כי לכל רשת זרימה, קיימת זרימת מקסימום חסרת מעגלים.

2

Answers

נסתכל על זרימת מקסימום עם מספר מעגלים מינימלי כך שהזרימה עליהם חיובית ממש. נניח בשלילה שקיים מעגל כזה נסתכל על קשת במעגל עם זרימה מינימלית מבין כל הקשתות במעגל ונחסיר את ערך הזרימה הזה מכל הקשתות במעגל. אפשר להשתכנע כי קיבלנו פונקציית זרימה עם פחות מעגלים עם זרימה חיובית ממש - סתירה.

1
Feedback