انجام پایان نامه

درخواست همکاری انجام پایان نامه  بانک مقالات رایگان انجام پایان نامه

سفارش پایان نامه

|

انجام پایان نامه ارشد

 پایان نامه 

پایان نامه‏ کامپیوتر

انجام پایان نامه‏ ارشد کامپیوتر

مقدمه:
   جريان در شبكه به معناي دقيق كلمه به معناي جريان نفت يا آب در سيستم خطوط لوله مي باشد. اغلب مواقع در نوشته هاي علمي، اين كلمه به جريان الكتريسيته، خطوط تلفن، پيامهاي الكترونيكي، كالاهايي كه از طريق جاده ها با كاميون حمل مي شوند يا انواع ديگر جريان اشاره مي كند. در واقع، غناي مسؤل شبكه-جـريان ماوراي اين كاربردها مي باشد. تئوري كلاسيك جريان شبكه، مـناطق متعدد و علي الظاهر نامرتبط بهينه سازي تركيبي را به يكديگر وصل مي كند. تعادل ها، در بين قضيه max-flow min-cut فورد و فولكرسون، قضيه هاي همبندي منجر(Menger) و قضيهmarriage فـيليپ هال منجر به شكل گيري و پيـرايش الگوريتم هاي مـفيدي براي تعدادي از مسائل كاربردي شده اند. اين مسائل عبارتند از: محاسبه نمودن همبندي يال و رأس نمودار و پيدا كردن زير مجموعه هاي خاص يال، كه تطبيق ناميده شده اند، كه براي حل مسائل مختلف جدول بندي و گمارش استفاده شده اند و در مناطق ديگر فعاليت هاي تحقيقاتي، علوم كامپيوتر و مهندسي كاربردهايي دارند.

1- جريانها و قطع ها در شبكه

   شبكه خط لوله براي انتقال نفت از يك منبع به مخزن اصلي، يك پروتوتايپ مدل شبكه است. هر قوسي قسمتي از خط لوله را نشان مي دهد و نقاط انتهايي قوس مطابق با اتصال هايي در انتهاي آنها پخش مي باشند. گنجايش قوس، مقدار ماكسيمم نفت است كه مي تواند در بخش مشابه در واحد زمان جاري شود. طبيعتاً شبكه سيستم خطوط جاده ها را براي حمل و نقل كالاها از يك نقطه به نقطه ديگر را نشان بدهد.

شبكه هاي پرظرفيت (Capacitated) يك منبع-يك مخزن
   تعريف: شبكه يك منبع-يك مخزن، يك نمودار متصل به هم است كه رأس مشخصي دارد كه منبع با outdegree غيرصفر ناميده شده است و رأس مشخصي كه مخزن باindegree غيرصفر ناميده شده است.
   اصطلاحات: شبكه يك منبع-يك مخزن با منبعsو مخزن(هدف) t اغلب تحت عنوان شبكهs-t ناميده شده است.
   تعريف: شبكه پرظرفيت يك نمودار متصل به هم است كه هر قوسe به تاق وزن مثبت اختصاص يافته است كه گنجايش قوسe ناميده شده است.
   نكته: بعداً در اين فصل، كاربردهاي مختلف بدون اتصال ظاهري به شبكه ها از طريق انتقال آنها در مسائل شبكه عنوان مي شوند، و از اين رهگذر توان و استحكام مدل شبكه را نشان مي دهند.
   اصطلاحات: فرض شده است كه تمامي شبكه هاي بحث شده در اين فصل شبكه هاي پرظرفيتs-t باشند حتي زماني كه يكي يا هر دوي تعديل كنندگان از بين رفته باشند.
   نكته: فرض كنيد كهvرأس در نمودارN باشد. سپسout(v) بر مجموعه تمامي قوس هايي دلالت دارد كه از رأس v بوجود آمده اند:
                                                                              Out(v) = {e Є EN | tail(e) = v }
مطابق با آن، in(v) بر مجموعه اي از تمام قوس هايي دلالت مي كند كه به سوي رأسv جهت گرفته اند.
                                                    In(v) = {e Є EN | head(e) = v }
   نكته: براي هر دو زير مجموعه رأسيXوY نمودارN، فرض كنيد كه<X,Y> بر مجموعه اي از تمام قوسهايي دلالت مي كنند كه از رأسي درX به رأسي درY جهت گرفته اند.
                         <X,Y> = {e Є EN | tail(e) Є X  and  head(e) Є Y }
   مثال1-1: شبكه پرظرفيتs-t 5 رأسي، در شكل 1-1 نشان داده شده است. اگر X={x,v}وY={w,t} باشد، سپس عوامل مجموعه قوس <X,Y> قوسي هستند كه از رأسيx به رأسw و از رأسv به مخزنt جهت گرفته اند. تنها عامل در مجموعه قوس<X,Y> قوسي است كه از رأسw به رأسv جهت يافته است.







   نكتـه: مـثال ها و كاربــردها در كل ايـن فصل مــستلزم شـبـكه هايي با گنجـايـش هاي اعــداد صـحيح مي باشند كه توضيح آن را آسان مي سازد. هيچ استلزام زيادي وجود ندارد اگر ظرفيت ها اعداد گوياي غير اعداد صحيح باشند. چنين شبكه اي را مي توان در يك شبكه هم ارز منتقل نمود كه گنجايش هاي آن اعـداد صحيح به واسطه ضرب نمودن هر گنـجايش در آخريـن مضرب مـشترك مخرج هاي گنجايـش ها مي باشند.

جريان هاي ممكن
   تعريف: فرض كنيد كه N شبكهs-t پر ظرفيت باشد. جريان(ممكن)f درN تابعf:EN      R+   است كه عدد حقيقي مثبتf(e) را به هر قوسe برمي گردد تخصيص مي دهد:
      (1) (قيود ظرفيت)f(e) ≤cap(e)، براي هر قوسe در شبكهN.                                                
      (2) (قيود پايستگي)∑e Є In(v)  f(e) = ∑e Є Out(v)  f(e)   ، براي هر رأسv در شبكهN، غير از منبع s و مخزنt.
   اصطلاحات: ويژگي2در تعريف جريان، حالت پايستگي جريان ناميده شده است. براي هر خط لوله نفت، بيان مي كندكه كل جريان نفت كه در هر اتصال(رأس)در خط لوله جريان دارد بايد برابر با كل جرياني باشد كه از همان اتصال خارج مي شود.
   نكـته: بـراي تـفكيك قايل از لحاظ بصري بين جريان و ظـرفيت قـوس، ما قراردادي را در طراحي ها برمي گزينيم زماني كه هر دو عدد وجود دارند، ظرفيت معمولاً به صورت خطوط لوله سياه و در سمت چپ جريان خواهد بود.
   مثال2-1: شكل2-1 جريان ممكن را براي شبكه مثال 1-1 نشان مي دهد. توجه داشته باشيدكه كل مـقدار جـريان كه از مـنبع s خـارج مي شود برابر با 6 است، كه جريـان خالـصي است كه وارد مـخزنt مي شود. جريان پايستگي در هر رأس داخلي در شبكه از لحاظ شهود با اين پديده تطبيق دارد. سپس در اين بخش، نتيجه 4-1 در كل به دست مي آيد كه خروج از منبع برابر با ورود به مخزن است.







   تعريف: مقدار شارشf در شبكه پرظرفيتN، كه به شكلval(f) نشان داده شده است، جريان خالصي است كه از مخزنs خارج مي گردد.
                         val(f) = ∑e Є Out(s)  f(e) - ∑e Є In(s)  f(e)
   تعريف: ماكسيمم جريانf* در شبكه پر ظرفيتN جرياني در N است كه ارزش ماكسيمم دارد. يعنيval(f) ≤val(f*) براي هر جريانf درN.

قطع در شبكه هاي s-t:
   براساس تـعريف، هر جريان غير صفر بايد حداقل از يكي از قـوس ها درout(s) استفاده كند. به عبارتي ديگر،‌اگر تمامي قوس ها درout(s) از شبكهN حذف شده باشد، سپس هيچ جرياني نمي تواند از مـنبعs وارد مـخزنt بشـود. ايـن مـوضوع حالت خاص تـعريف ذيـل مي بـاشد، كه مفـاهيم افرازـ قطع(from  §4.6) و مجمـوعه تفكيك كننده s-t (from §5.3) را با هم تـركيب و تلفيق مي كند.
   تعريف: فـرض كنيد كه N شبكهs-t بـاشد و Vs وVt افـرازVn را تـشكيل بدهند به گونه اي كه مـنبعs Є Vs و مخزنt Є Vt باشد. سپس مجموعه تماس قوس هايي كه از رأس در مجموعه Vs به رأس در مجموعهVt هدايت شده اند، s-t قطع شبكه N ناميده شده است و به شكل <Vs,Vt> نشان داده شده است.
   نكته: توجه داشته باشيد كه مجموعه قوسout(s) برايs-t شبكهN قطعs-t <{s},VN-{s}> باشد. In(t)، قطعs-t <{VN-{t},{t}> است.
   مثال3-1: شكل 3-1 مجمـوعه هاي قـوسout(s) وin(t) را به شكل قطع هايs-t به تصوير مي كشد، در حالي كه
                    Out(s) = <{s}, {x,v,w,t}>   and   In(s) = <{s,x,v,w},{t}>













   مثال4-1:  قطع s-t متداول تر<Vs,Vt> در شكل4-1 نشان داده شده است، در حاليكهVs={s,x,v} وVt={w,t}.









   گزاره1-1: فرض كنيد كه<Vs,Vt> قطعs-t شبكهN باشد. سپس هر مسيرs-t جهت يافته درN حداقل داراي يك قوس در<Vs,Vt> است.
   اثبات: فرض كنيد كهP = <s=V0,V1,V2,…,Vt=t>توالي رأس جهت يافته مسيرs-t در شبكهN باشد. از اينرو s Є Vs و  t Є Vt است. نخستين رأسVj در اين مسير مي باشد كه در مجموعهVt است(شكل 5-1 را ببينيد). سپس قوس از رأسVj-1 بهVjدر<Vs,Vt> مي باشد.







رابطه بين جريان ها و قطع ها
   همانند بررسي مجموعهout(s) قوس جهت يافته از منبعs به شكل قطعs-t   <{s},VN-{s}> و مجموعهin(s) ممكن است به عنوان مجمـوعه قوس هاي پر و مثبت به اين قطع يعني مجموعه قوس<VN-{s},{s}> تلقي شوند. براساس اين ديدگاه، تعريفval(f) اين گونه نوشته مي شود:
                    val(f) = ∑e Є <{s},VN-{s}>  f(e) - ∑e Є <VN-{s},{s}>  f(e)
 به عبارتي ديگر، ارزش هر جريان مساوي با كل جريان در قوس هاي قطع<{s},VN-{s}> منهاي جريان در قوس هاي<VN-{s},{s}> است. گزاره بعد اين خصوصيت را به تمامي قطع هايs-t تعميم مي دهد. اثبات آن از توالي ساده تعاريف زير استفاده مي كند.
   لم 2-1: فرض كنيد كه<Vs,Vt> در قطعs-t شبكهs-t، ازN باشد از اينرو:
    Uv Є Vs  Out(v) = <Vs,Vs>U<Vs,Vt>  and  Uv Є Vs  In(v) = <Vs,Vs>U<Vt,Vs>
   اثبـات: براي هـر رأس v Є Vs، هر قـوس جـهت يافته ازv يا در<Vs,Vs> يا در<Vs,Vt> اسـت(شكل 6-1 براي هر رأسV، افرازout(v)‌ را در زير مجموعه چهار عضوي<Vs,Vs> و زير مجموعه سه عضوي<Vt,Vs> نشان مي دهد). همينطور، در قوس جهت يافته از رأسV يا در<Vs,Vs> يا در<Vt,Vs> است.






   گزاره3-1: فرض كنيد كهf جريانs-t در شبكهN‌باشد و<Vs,Vt> هرs-t قطعN باشد.
                   val(f) = ∑e Є <Vs,Vt>  f(e) - ∑e Є <Vt,Vs>  f(e)
اثبات:
                            val(f) = ∑e Є Out(s)  f(e) - ∑e Є In(s)  f(e)
          ∑e Є Out(v)  f(e) - ∑e Є In(v)  f(e) = 0                    v Є Vs
                           val(f) = ∑ v Є Vs  (∑e Є Out(v)  f(e) - ∑e Є In(v)  f(e)) =       
     ∑ v Є Vs ∑e Є Out(v)  f(e) - ∑ v Є Vs  (∑e Є in(v)  f(e)
   ∑ v Є Vs ∑e Є Out(v)  f(e) = ∑e Є <Vs,Vs>  f(e) + ∑e Є <Vs,Vt>  f(e)
      ∑ v Є Vs ∑e Є in(v)  f(e) = ∑e Є <Vs,Vs>  f(e) + ∑e Є <Vs,Vt>  f(e)
   مـثال 5-1: جـريانf و قطع{s,x,v},{w,t} كه در شـكل1-1 نـشان داده شـده اند، گزاره3-1 را نـشان مي دهند.   








نتيجه بعد اثبات مي كند كه چه چيزي قبل از اين شهود آشكار بود، يعني كه، جريان خالص خارج از منبعs مساوي جريان خالص در مخزنt است.
   نتيجه 4-1: فرض كنيد كهf جريان در شبكهs-t باشد، پس:
                      val(f) = ∑e Є In(t)  f(e) - ∑e Є Out(t)  f(e)
   اثبات: با استفاده از گزاره 3-1 در s-t  cut ، in(t)= <VN-{t},{t}> است.
   تعريف: ظـرفيتcut <Vs,Vt> ، كه دلالـت بر<Vs,Vt> مي كند، مجمـوع ظرفيت هاي قوس ها درcut  <Vs,Vt> است. يعني:
                             cap<Vs,Vt> = ∑e Є <Vs,Vt>  cap(e)
   تعريف: مينيممcut از شبكهN قطع با ظرفيت مينيمم است.
   مثال6-1: ظرفيت قطع در شكل 7-1، برابر با 13 است وcut<{s,x,v,w},{t}> با ظرفيت 10 فقط قطع مينيمم است.

مسأله ماكسيمم-جريان و مسأله مينيمم-قطع
   چند نتيجه بعد نشان مي دهند كه مسائل پيدا كردن ماكسيمم جريان در شبكه با ظرفيتN و پيدا كردن مينيمم-قطع درN كاملاً با يكديگر مربوط مي باشند. در واقع، اين در مسأله بهينه سازي، جفت max,min را بوجود مي آورند، كه شبيه جفتmax-min مي باشد كه در §5.3 مشخص است. نتيجه نخست كران بالا را براي مسأله ماكسيمم-جريان شرح مي دهد.
   گزاره5-1: فرض كنيد كهf هر جرياني درs-t شبكهN باشد و<Vs,Vt> ، s-t قطع است.
                                           val(f) ≤ cap<Vs,Vt>
   اثبات: زنحيره نامعادله هاي زير كه با تصديق گزاره3-1 شروع مي شود كه اين نتيجه بدست مي آيد.
                 val(f) = ∑ e Є <Vs,Vt>  f(e) - ∑ e Є <Vt,Vs>  f(e)
                   ≤ ∑ e Є <Vs,Vt>  (e) - ∑ e Є <Vt,Vs>  f(e)
                          = cap<Vs,Vt> - ∑ e Є <Vt,Vs>  f(e)
                                                      cap<Vs,Vt>  ≤

نتيجه ذيل شبيه نتيجه دوگانگي ضعيف در §5.3 است(گزاره1-3-5).
   نتـيجه 6-1(دوگانـگي ضـعيف): فـرض كنيـد كهf* مـاكسيمم جــريان درs-t شبـكهN بـاشد وK* مـينيممs-t‌قطع درN باشد.
                                             val(f*) ≤ cap(K*)

   اثبات: اين، نتيجه مياني گزاره 5-1 است. نتيجه 7-1(اثبات بهينگي). فرض كنيد كهf جريان درs-t شبكهN و K، قطعs-t باشد و فرض كنيد كهval(f)=cap(k) است. سپس جريانf ماكسيمم جريان در شبكهN است و cut  k مينيمم قطع مي باشد.
                                              val(fˆ) ≤ cap(K*) = val(f)
   اثبات: فرض كنيد كهf هر جريان ممكني در شبكهN مي باشد. زنجيره ذيل، كه ماكسيمال بودن جريانf را اثبات مي كند، نتيجه گزاره5-1 و مقدمه است. ماكسيمال بودنcut  k را مي توان با استدلال مشابهي اثبات نمود و به عنوان يك تمرين تلقي شده است.
   مثال7-1: جريان براي شبكه نمونه نشان داده شده در شكل 8-1، ارزش 10 دارد، كه ظرفيت قطعs-t  <{s,x,v,w},{t}> نيز مي باشد. بواسطه نتيجه7-1، هم جريان و هم قطع براي مسائل بعدي آنها مطلوب مي باشند.







نتيجه نهايي اين بخش كه در فصل بعد استفاده شده است، رسم نمودن الگوريتم كلاسيك براي پيدا كردن جريان ماكسيمم در شبكه مي باشد.
   نتيجه8-1: فرض كنيد كه<Vs,Vt> قطعs-t در شبكهN باشد و فرض كنيد نماييد كهf جرياني بدينگونه باشد، سپسf جريان ماكسيمم درN و<Vs,Vt> قطع مينيمم است.
                                                                                  { f(e) =
 

















2- حل كردن مسأله ماكسيمم-جريان

   تصور كلي الگوريتم داده شده در اين بخش، كه توسط فورد و فولكرسون مطرح شده است، اضافه نمودن جريان در شبكه به طور مكرر مي باشد تا جايي كه از اين بيشتر اضافه نشود. هر افزايش براساس توالي انتخاب شده متناوب رأس ها و قوس ها مي باشد كه مسير افزايشي ناميده شده است. قبل از ارائه اصول كلي اين مسير، ما ساده ترين و بديهي ترين اصول را بررسي مي نماييم.

استفاده از مسيرهاي مشخص براي افزايش جريان
   فرض كنيد كهf جرياني در شبكهs-t با ظرفيتN است و مسير مشخصs-t نيز درN وجود دارد:
                                        P = <s,e1,v1,e2,…,ek,t>
بطوريكهf(ei)<cap(ei) برايi=1,…,k . سپس فقط ظـرفيت ها را بـررسي نماييد. جريان هر قوسei را مي توان تاcap(ei)-f(ei) افزايش داد. اما براي فقط ويژگي پايستگي جريان در هر يك از رأس هايVi ، افزايش ها در تمامي قوس هاي مسيرp بايد برابر باشند. از اينرو، اگر∆p دلالت بر اين افزايش كند، سپس بزرگترين ارزش ممكن براي∆p برابر با{cap(ei)-f(ei)} است.
   مثال1-2: در شبكه نمونه نشان داده شده در سمت چپ در شكل1-2، مقدار جريان فعلي 6 است. مسير جهت دارs-t راp=<s,x,w,t> در نظر بگيريد. جريان در هر قوس مسيرp را مي توان در∆p=2 افزايش داد و جريان بدست آمده، كه ارزش 8 دارد، در سمت راست نشان داده شده است.








انجام پایان نامه

انجام پایان نامه کامپیوتر، انجام پایان نامه ارشد کامپیوتر، انجام پایان نامه، پایان نامه

برای دیدن ادامه مطلب از لینک زیر استفاده نمایید

  دانلود مقاله | انجام پایان نامه

سفارش پایان نامه

نقشه