دانلود با لینک مستقیم و پر سرعت .
مقدمه:
جریان در شبکه به معنای دقیق کلمه به معنای جریان نفت یا آب در سیستم خطوط لوله می باشد. اغلب مواقع در نوشته های علمی، این کلمه به جریان الکتریسیته، خطوط تلفن، پیامهای الکترونیکی، کالاهایی که از طریق جاده ها با کامیون حمل می شوند یا انواع دیگر جریان اشاره می کند. در واقع، غنای مسؤل شبکه-جـریان ماورای این کاربردها می باشد. تئوری کلاسیک جریان شبکه، مـناطق متعدد و علی الظاهر نامرتبط بهینه سازی ترکیبی را به یکدیگر وصل می کند. تعادل ها، در بین قضیه 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 دارد، در سمت راست نشان داده شده است.
با استفاده از مـسیر جهت دار<s,v,t>، جـریان را می توان تا 9 افزایش داد. جریان بدست آمده در شکل2-2 نشـان داده است. در این مـسیر، جریان را نمی توان بیشتر از این در امـتداد مسیرهای جهت دارs-t افزایش داد، چون هر مسیر باید یا از قوس جهت دار منبعs به رأسx یا از رأسv به مخزنt استفاده نماید و این دو قوس در ظرفیت جریان دارند.
به هر حال، جریان را می توان بیـشتر افزایش داد. یک روش برای انجام این کار، افـزایش دادن جریان برروی قوس از منبعs به رأسv از طریق یک واحد، کاهش جریان در قوس ازw بهv در یک واحد افزایش جریان در قوس ازw بهt از طریق یک واحد می باشد. کاهش در جریان برروی قوس ازw بهv برجهت یابی مجدد یک واحد جریان از رأسv تأثیر دارد، از اینرو به جای رفتن به سمت رأسv، مستقیماً به سمت مخزنt می رود. این امر فضایی را برای واحد اضافی جریان برروی قوس از منبعs به رأسv بوجود می آورد.
نکته: توجه داشته باشید که در افزایش جریان از 9 به 10 در شبکه نمونه، قوسی که جریان آن افزایش یافته است مسیرs-t را بوجود می آورد، اگر جهات آن نادیده گرفته شوند. تعمیم مسیر جهت دار در جایگزین استراتژی موقت استفاده شده بالا با استراتژی سیستماتیک کمک می کند.
مسیرهای افزایشیf
تعریف: شبه مسیرs-t در شبکهN توالی متناوب رأس ها و قوس هایی است که مسیرs-t را در نمودار اصلیN بوجود می آورد.
<s=v0,e1,v1,…,vk-1,ek,vk=t>
اصطلاحات: برای شبه مسیر خاصs-t، قوسei پیشرو نامیده شده است:
Q = <s=v0,e1,v1,…,vk-1,ek,vk=t>
اگر از قوسvi-1 به رأسvj جهت یافته باشد و قـوسei قوس پسرو نامیده می شود اگر ازvj به سمتvj-1 جهت گرفته باشد.
نکته: علی الظاهر، مسیرs-t جهت دار شبه مسیری است که تمامی قوس های آن پیشرو می باشد.
نکته اصطلاح شناسی: بعضی از نویسندگان از اصطلاح نیمه مسیر به جای شبه مسیر استفاده می کنند.
مثال2-2: در شبه مسیرs-t نشان داده شده در شکل3-2 قوس هایa وb پسرو و سه قوس دیگر پیشرو می باشند.
تعریف: فرض کنید کهf جریانs-t شبکهN باشد. مسیرf افزایشیQ شبه مسیرs-t درN است بطوریکه جریان در هر قوس پیشرو را بتوان افزایش داد و جریان در هر قوس پسرو را می توان کاهش داد. از اینرو، برای هر قوسe در مسیرf افزایشیQ:
f(e) > cap(e), if e is a forward arc
f(e) < 0, if e is a backward arc
نکته: برای هر قوسe در مسیرf افزایشیQ، فرض کنید که∆e کمیت خاصی باشد.
{
اصطلاحات: کمیت∆e کمکی برروی قوسe نامیده شده است. مقدار آن در قوس پیشرو بزرگترین افزایش احتمالی در جریان است و برروی قوس پسرو، بیشترین کاهش ممکن در جریان، قطع نظر از پایستگی جریان می باشد.
نکته: پایستگی جریان نیاز به این دارد که تغییر در جریان برروی قوس های مسیر افزایشی جریان قدر یکسان داشته باشد. از اینرو، ماکسیمم تغییر مجاز در جریان برروی قوس شبه مسیرQ، ∆Q می باشد.
∆Q = min {∆e}
توجه داشته باشید که این تعریف∆Q، با∆p قبلاً تعریف شده انطباق دارد، هر زمانی که شبه مسیرQ مسیر جهت دار باشد.
مثال3-2: برای شبکه نمونه در شکل4-2، جریان فعلیf ارزش 9 دارد و شبه مسیرQ=<s,v,w,t> مسیر افزایشیf با∆Q=1 است.
اصطلاحات: برای ساده نمودن اصطلاحات، پیشوند شبه در تعریف مسیر افزایشیf استفاده نشده است.اما برای تأکید نمودن بر این اصل که مسیر افزایشیf الزاماً مسیر جهت دار نیست، حرفQ غالباً به عنوان شبه مسیر ها استفاده شده است. گزاره ذیل خلاصه می کند که جگونه مسیر افزایشیf برای افزایش جریانf در شبکه استفاده شده است.
گزاره1-2: (افزایش جریان) فرض کنید کهf جریان در شبکهN وQ مسیر افزایشیf با مینیمم کمک ∆Q بر روی قوس های آن می باشد. از این رو جریان افزایشیf اینگونه نشان داده شده است:
fˆ(e) = {
که جریان ممکن در شبکهN و val(fˆ) = val(f)+ ∆Q است.
اثبات: علی الظاهر، 0 ≤ fˆ(e) ≤ cap(e) به واسطه تعریف∆Q است. فقط رأس هایی که در جریان خالص ممکن است تغییر یابند رأس ها بر روی مسیر افزایشQ می باشند. از این رو، برای اثبات این کهf پایستگی جریان را ارضا می کند، فقط رأس های داخلیQ نیاز به بررسی دارند. برای رأسV در مسیر افزایشیQ، دو قوسQ که درV لازم می باشند به یکی از چهار روش ذیل پیکره بندی شده اند، همان طورکه در شکل5-2 نشان داده شده اند. در هر حالت، جریان خالص در داخل یا خارج از رأسV تغییری نمی کند. از این رو مانع ویژگی پایستگی جریان می شوند.
این شکل نشان داده است که جریان در∆Qافزایش یافته است. تنها قوسی که بر روی منبعS بخش لازمه است، که جریان آن افزایش یافته است. نخستین قوسei مسیر افزایشیQ است. اگرei قوس پیشرو باشد سپس fˆ(ei)=f(ei)+∆Q و اگرei قوس پسرو باشد، سپس fˆ(ei)=f(ei)- ∆Q است.
val(fˆ) = ∑e Є Out(s) fˆ(e) - ∑e Є In(s) fˆ(e)
نتیجه2-2: فرض کنیدf جریان افزایشی عدد صحیح در شبکهN باشد که ظرفیت های قوس آن اعداد صحیح می باشند.از این رو جریانی که از افزایش هر جریان متوالی ناشی می شود عدد صحیحی خواهد بود.
قضیه Max-Flow Min-cut
قضیه3-2: [خصوصیت جریان ماکسیمم]. فرض کنید کهf جریان در شبکهN باشد. از این روf ماکسیمم جریان در شبکهN است. اگر مسیر افزایشیf درN وجود نداشته باشد.
اثبات: فرض کنید کهfماکسیمم جریان در شبکهN باشد. از این رو به واسطه گزاره1-2، هیچ مسیر افزایشیf وجود ندارد. (بسندگی) فرض کنید که مسیر افزایشیf در شبکهN وجود ندارد. مجموع تمامی شبه مسیر ها را در شبکهN در نظر بگیرید که با منبعS شروع شود و فرض نمایید کهVs اجتماع مجموعه ها- رأس های شبه مسـیرها باشد-از این رو هیچ مسیر افزایشیf وجود ندارد، نشان می دهد که مخزن t ¢Vs است. فرض نمایید کهVt = Vn-Vs است. سپس<Vs,Vt> قطعs-t شبکه می باشد. علاوه بر این، به واسطه تعریف مجموعه هایVs و Vt،
{ f(e) =
f ماکسیمم جریان در نتیجه8-1 است.
قضیه4-2: [Max-Flow Min-cut]. برای شبکه خاص، مقدار ماکسیمم جریان مساوی با ظرفیت مینیمم قطع است.
اثبات: قطعs-t که بر اساس اثبات قضیه 3-2 شکل گرفته است، ظرفیتی مساوی با ماکسیمم جریان دارد. رئوس کلی الگوریتیم برای ماکسـیمم نمودن جریان در شبکه ناشـی از فرضیه1-2 و قضیه3-2 است.
Algorithm 2.1: Outline for Maximum Flow
Input: an s-t network N
Output: a maximum flow f* in network N
[initialization]
For each arc e in network N
f* (e):= 0
[Flow Augmentation]
while there exists an f-augmenting path in network N
find an f*-augmenting path Q
Let ∆Q=min eЄQ {∆e}
For each arc e of augmenting path Q
If e is a forward arc
f *(e):=f*(e)+ ∆Q
Else (e is a backward arc)
f *(e):=f*(e)- ∆Q
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 20 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
