בעית מקסימום זרימה

[asmade]

שלום,

 

אחד ממשפטי העזר בבעית מקסימום זרימה הוא:

f(s,N) - f(N,s) = f(N,t) - f(t,N) = V(f)

 

אני לא מצליח להבין את משמעות המשפט, האם מישהו יכול להציג דוגמא מוחשית עפ"י נתוני הגרף המצורף.

אם אפשר להסביר גם את ההוכחה זה יעזור מאוד.

 

תודה

[Home@]

תוכל לפרט מה משמעות הסימונים האלה עבורכם?

[asmade]

f - flow - זרימה

על הגרף הערך השמאלי הוא הקיבולת (capacity) והימני הוא הזרימה (flow).

[Home@]

מה זה V? מה זה N (אני מתאר לעצמי שחתך s-t כלשהוא?) ומה המשמעות של http://www.codecogs.com/gif.latex?f(s,%20N)?

[asmade]

V - הזרימה

N - לא כ"כ ברור לי מזה, אולי N = קודקוד כלשהו

[asmade]

f(s,N) = הזרימה בין הקשתות S-N

[Home@]

אני אניח פה ש-http://www.codecogs.com/gif.latex?f(s,N) היא הזרימה היוצאת מ-s לשאר הרשת, כי אני לא רואה פירוש אחר שתחתיו המשפט הזה נכון.

 

מה שהמשפט אומר בעצם הוא שנטו הזרימה שיוצאת מהמקור (הזרימה היוצאת מ-s לשאר הרשת פחות הזרימה הנכנסת ל-s) שווה לנטו הזרימה שנכנסת לבור (הזרימה הנכנסת ל-t פחות הזרימה היוצאת ממנו). באופן אינטואיטיבי, זה אומר שאין יח' זרימה ש-"הולכות לאיבוד" בדרך מהמקור לבור. מהמשפט גם ניתן להסיק כי אף על פי שעוצמתה של פונקציית זרימה מוגדרת כזרימה נטו היוצאת מהמקור, אפשר גם להגדיר אותה כזרימה הנכנסת לבור ולמעשה גם כזרימה נטו החוצה כל חתך s-t של הרשת.

 

בדוגמה המצורפת יוצאות מהמקור 4 יח' זרימה ואחת נכנסת, ולכן הזרימה נטו היוצאת מ-s היא 3, וזו גם בדיוק הזרימה הנכנסת ל-t.

[asmade]

תודה