שאלה באלגוריתמים.
נתונה רשת זרימה שבה בנוסף לחסמים העליונים c(e) zzz על הקשתות יש גם חסם תחתון b(e) zzz על כל קשת, כלומר הזרימה בקשת f(e) ,e,צריכה לקיים b(e)<=f(e)<=c(e) zzzz. מהם השינויים הנדרשים באלגוריתם של Ford-Fulkerson כדי להתאימו למציאת זרימה מקסימלית תחת תנאים אלה, כאשר נתונה זרימה חוקית ברשת? הפתרון הוא כזה: נשנה את האלגוריתם כך שלכל קשת (u,v) של הגרף, תהיה בקשת השיורית קשת (u,v) עם c'(u,v)=c(u,v) - f(u,v) zzz וקשת (v,u) עם c'(v,u)=f(u,v) - b(u,v) zzz. מדוע הפתרון הזה עובד? תודה מראש.
נתונה רשת זרימה שבה בנוסף לחסמים העליונים c(e) zzz על הקשתות יש גם חסם תחתון b(e) zzz על כל קשת, כלומר הזרימה בקשת f(e) ,e,צריכה לקיים b(e)<=f(e)<=c(e) zzzz. מהם השינויים הנדרשים באלגוריתם של Ford-Fulkerson כדי להתאימו למציאת זרימה מקסימלית תחת תנאים אלה, כאשר נתונה זרימה חוקית ברשת? הפתרון הוא כזה: נשנה את האלגוריתם כך שלכל קשת (u,v) של הגרף, תהיה בקשת השיורית קשת (u,v) עם c'(u,v)=c(u,v) - f(u,v) zzz וקשת (v,u) עם c'(v,u)=f(u,v) - b(u,v) zzz. מדוע הפתרון הזה עובד? תודה מראש.