تحقیق مقاله جریان ها و کاربرد های شبکه

مقدمه:

   جریان در شبکه به معنای دقیق کلمه به معنای جریان نفت یا آب در سیستم خطوط لوله می باشد. اغلب مواقع در نوشته های علمی، این کلمه به جریان الکتریسیته، خطوط تلفن، پیامهای الکترونیکی، کالاهایی که از طریق جاده ها با کامیون حمل می شوند یا انواع دیگر جریان اشاره می کند. در واقع، غنای مسؤل شبکه-جریان ماورای این کاربردها می باشد. تئوری کلاسیک جریان شبکه، مناطق متعدد و علی الظاهر نامرتبط بهینه سازی ترکیبی را به یکدیگر وصل می کند. تعادل ها، در بین قضیه 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 جهت گرفته اند.

                         = {e Є EN | tail(e) Є X  and  head(e) Є Y }

   مثال1-1: شبکه پرظرفیتs-t 5 رأسی، در شکل 1-1 نشان داده شده است. اگر X={x,v}وY={w,t} باشد، سپس عوامل مجموعه قوس قوسی هستند که از رأسیx به رأسw و از رأسv به مخزنt جهت گرفته اند. تنها عامل در مجموعه قوس قوسی است که از رأس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 نامیده شده است و به شکل نشان داده شده است.

   نکته: توجه داشته باشید که مجموعه قوس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}>

  گزاره1-1: فرض کنید که قطعs-t شبکهN باشد. سپس هر مسیرs-t جهت یافته درN حداقل دارای یک قوس در است.

   اثبات: فرض کنید کهP = توالی رأس جهت یافته مسیرs-t در شبکهN باشد. از اینرو s Є Vs و  t Є Vt است. نخستین رأسVj در این مسیر می باشد که در مجموعهVt است(شکل 5-1 را ببینید). سپس قوس از رأسVj-1 بهVjدر می باشد.

رابطه بین جریان ها و قطع ها

   همانند بررسی مجموعهout(s) قوس جهت یافته از منبعs به شکل قطعs-t   <{s},VN-{s}> و مجموعهin(s) ممکن است به عنوان مجموعه قوس های پر و مثبت به این قطع یعنی مجموعه قوس تلقی شوند. براساس این دیدگاه، تعریفval(f) این گونه نوشته می شود:

                    val(f) = ∑e Є <{s},VN-{s}>  f(e) - ∑e Є   f(e)

 به عبارتی دیگر، ارزش هر جریان مساوی با کل جریان در قوس های قطع<{s},VN-{s}> منهای جریان در قوس های است. گزاره بعد این خصوصیت را به تمامی قطع هایs-t تعمیم می دهد. اثبات آن از توالی ساده تعاریف زیر استفاده می کند.

   لم 2-1: فرض کنید که در قطعs-t شبکهs-t، ازN باشد از اینرو:

    Uv Є Vs  Out(v) = U  and  Uv Є Vs  In(v) = U

s

   اثبات: برای هر رأس v Є Vs، هر قوس جهت یافته ازv یا در یا در است(شکل 6-1 برای هر رأسV، افرازout(v)‌ را در زیر مجموعه چهار عضوی و زیر مجموعه سه عضوی نشان می دهد). همینطور، در قوس جهت یافته از رأسV یا در یا در است.

   گزاره3-1: فرض کنید کهf جریانs-t در شبکهN‌باشد و هرs-t قطعN باشد.

                   val(f) = ∑e Є   f(e) - ∑e Є   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 Є  f(e) + ∑e Є   f(e)

      ∑ v Є Vs ∑e Є in(v)  f(e) = ∑e Є   f(e) + ∑e Є   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)= است.

   تعریف: ظرفیتcut ، که دلالت بر می کند، مجموع ظرفیت های قوس ها درcut  است. یعنی:

                             cap = ∑e Є   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 باشد و ، s-t قطع است.

                                           val(f) ≤ cap

   اثبات: زنحیره نامعادله های زیر که با تصدیق گزاره3-1 شروع می شود که این نتیجه بدست می آید.