[-] שאלה 1 א
by ilanede - Monday, 6 July 2009 22:44:05

אם יש פונקציית זרימה ונתונה לנו הרשת השיורית של הזרימה האם מכל  פונקיית זרימה ניתן להגיע בעזרת הרשת השיורית לזרימה  מקסימלית.
אם כן אז סעיף א' לא נובע מיידית מסעיף 4.1 באלגוריתם עבור K=0
כי ניתן לתקן את כל מה שעשינו עד השלב  שבו
K=0?

thread
[-] Re: שאלה 1 א
by abuaffas - Monday, 6 July 2009 23:25:16
When k=0, you find a flow g only in Nf(0). What about the flow you found in the former steps?
thread
[-] Re: שאלה 1 א
by ilanede - Monday, 6 July 2009 23:26:42
we don't care since we can undo all the bad decisions we made in the former steps   
thread
[-] Re: שאלה 1 א
by abuaffas - Tuesday, 7 July 2009 00:01:48
There are no bad decisions, this the point.
You need to show that the maximal flow is equal to g1+g2+.....
thread
[-] Re: שאלה 1 א
by idanbach - Tuesday, 7 July 2009 00:24:08

הנקודה שהיא שלא חשוב אם ההחלטות הקודמות שקיבלנו היו טובות או לא,אלא שבשלב ש K=0
עבור זרימה כלשהי שנתונה לנו עם הרשת השיורית שמתאימה לה, נפעיל את האלגוריתם למציאת זרימה מקסימלית וברור שנקבל זרימה מקסימלית בלי קשר לשלבים הקודמים.

thread
[-] Re: שאלה 1 א
by abuaffas - Tuesday, 7 July 2009 00:48:55

אם יש לך זרימה ורשת שיורית המתאימה לזרימה זו, אזי אתה תקבל זרימה מקסימלית ברשת השיורית (לא ברשת כולה), ויחד עם הזרימה שנתונה לך, אתה מקבל את הזרימה המקסימלית ברשת כולה.
אני מקווה שהייתי ברור.

thread
[-] Re: שאלה 1 א
by idoi - Tuesday, 7 July 2009 12:23:16
רק לוודא, את הזרימה המקסימלית
g
מוצאים בכל פעם ברשת הזרימה השיורית, כאשר היא מתעדכנת לאחר כל איטרציה (כלומר לאחר מציאת g
באיטרציה הקודמת, עדכנו את הרשת השיורית) ?
thread
Re: שאלה 1 א
by abuaffas - Tuesday, 7 July 2009 12:45:45
כן.
thread
[-] Re: שאלה 1 א
by anatba - Tuesday, 7 July 2009 13:00:04

    האם צריך להוכיח ש:
g(N'f)+g(N''f)=g(N'f+N''f)?

thread
Re: שאלה 1 א
by abuaffas - Tuesday, 7 July 2009 13:06:30
לא הבנתי.
thread