قله بلند
دوشنبه 24 آبان 1389, 17:36 عصر
با سلام
من یه طرح کلی از این الگوریتم رو متوجه شدم ولی هنوز اتفاقاتی که در حین اجرای این الگوریتم می افته رو متوجه نشدم.
می دانیم منبع در ارتفاع V قرار دارد و چاه و بقیه گره های میانی نیز روی زمین هستند.
1-قضیه جریان پیش جریان چیست؟ آیا این جریان همان میزان ظرفیت هر لوله خارج شده از منبع است؟
2-چرا این پیش جریان وجود داره؟
3-وقتی گره ای سریز کرد، ارتفاعش یک واحد افزایش می یابد تا چه اتفاقی بیافتد؟ جریان را به سمت گره بعدی هدایت کند و یا اینکه جریان اضافی را به لوله ای بفرستد تا در جای دیگری انبار شود؟
4-یکی از لم ها می گوید که این افزایش ارتفاع می تواند تا
h[u]<=2h[V]-1
باشد. یعنی هر گره ای که در مسیر قرار دارد می تواند تا بالای سر منبع هم پیش برود تا جریان اضافی را به منبع بازگرداند؟ می شه بیشتر این موضوع رو توضیح بدید؟
سپاس
من یه طرح کلی از این الگوریتم رو متوجه شدم ولی هنوز اتفاقاتی که در حین اجرای این الگوریتم می افته رو متوجه نشدم.
می دانیم منبع در ارتفاع V قرار دارد و چاه و بقیه گره های میانی نیز روی زمین هستند.
1-قضیه جریان پیش جریان چیست؟ آیا این جریان همان میزان ظرفیت هر لوله خارج شده از منبع است؟
2-چرا این پیش جریان وجود داره؟
3-وقتی گره ای سریز کرد، ارتفاعش یک واحد افزایش می یابد تا چه اتفاقی بیافتد؟ جریان را به سمت گره بعدی هدایت کند و یا اینکه جریان اضافی را به لوله ای بفرستد تا در جای دیگری انبار شود؟
4-یکی از لم ها می گوید که این افزایش ارتفاع می تواند تا
h[u]<=2h[V]-1
باشد. یعنی هر گره ای که در مسیر قرار دارد می تواند تا بالای سر منبع هم پیش برود تا جریان اضافی را به منبع بازگرداند؟ می شه بیشتر این موضوع رو توضیح بدید؟
سپاس