7037

مهدي خطابي

كارشناسي ارشد

رياضي كاربردي

پيام نور , كتابخانه مركزي دانشگاه پيام نور

1391

شير دل ، غلام حسن

فرهمند راد، شهريار

55ص

54ص

پ خطابي ، مهدي , ع

مسئله ماكسيمم جريان مقيد عبارتست از، ارسال بيشترين جريان ممكن در شبكه بطوريكه تمامي هزينه هاي جريان فراتر از بودجه تعيين شده نباشد .هرچند مسئله ماكسيمم جريان در شبكه ها از ديرباز مورد توجه محققان بوده ، با اين حال محققين همواره نگران پيچيدگي زماني الگوريتم هاي حل مسئله ماكسيمم جريان بوده صاند و لذا الگوريتمهايي را در خصوص تسريع حل اين مسئله ارائه كردند كه بعضا منجر به بهبود كارايي و تسريع در حل مسائل شبكه ها شده است .در اين پايان نامه براي حل مسايل ماكسيمم جريان ، يك الگوريتم پيشنهاد شده ، كه از دو نقطه نظر تئوري و كاربردي مورد بررسي قرار مي گيرد و مي تواند زمينه را براي طرح ايده هايي مفيد و كاربردي در مسائل شبكه ها فراهم كند .در واقع در اين روش ما با ارائه مفاهيم جديدي در شبكه مانند كمان وارد شونده زير درخت و كمان داخلي زير درخت متغيرهاي دوگان سيمپلكس را محاسبه نموده و الگوريتمي ارائه كرده ايم كه پيچيدگي زماني بهتري نسبت به ديگر الگوريتم ها دارد و لذا مسئله ماكسيمم جريان را در مرتبه زماني بهتري نسبت به ساير الگوريتم ها حل مي كند

فصل اول : تعاريف و كليات . فصل دوم : دوگان الگوريتم سيمپلكس ويژه . فصل سوم : محورگيري و بهينگي الگوريتم . فصل چهارم : نتايج الگوريتم

2931/10/71

7037پ

1

20876