שאלה

[loving angel1]

שאלה

היי. באחד התרגולים שהיו לנו לא מזמן בנושא רשת זרימה, קיבלנו שאלה לחשיבה (שנראה לי שהיא גם תופיע בבחינה, כי טרם קבילנו לה תשובה וגם לא נקבל ככל הנראה). השאלה היא : נתונה רשת זרימה G עם פונקצית קיבול אי שלילית C על הקשתות, ונתונה קשת e(x,y. יש לתאר אלגוריתם המוצא זרימה (לאו דווקא מקסימלית) ברשת, שעבודה גודל הזרימה על הקשת E הוא מקסימלי. אשמח לקבל רעיונות,כי הרעיון היחיד שהיה לי עד עכשיו הוא "למחוק" את הקשת מהגרף ולחבר אותה ישירות למקור ולבור אך הבעיה שנראה לי שבעצם אני מדלגת על הגרף

 

[loving angel1]

help plz

 

[loving angel1]

מקפיצה...

האם יש למישהו מושג איך פותרים את השאלה שלי?

 

[עדין ר]

סתם רעיון

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

 

[עדין ר]

אופס

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