جریانها و کاربردهای شبکه
ـ جریانها و قطع ها در شبکه
ـ حل نمودن مساله جریان ماکزیمم
ـ تعیین نمودن همبندی نمودار
ـ تطابق ها، خطوط مورب و پوشش های راسی
مقدمه:
جریان در شبکه به معنای دقیق کلمه به معنای جریان نفت یا آب در سیستم خطوط لوله می باشد. اغلب مواقع در نوشته های علمی، این کلمه به جریان الکتریسیته، خطوط تلفن، پیامهای الکترونیکی، کالاهایی که از طریق جاده ها با کامیون حمل می شوند یا انواع دیگر جریان اشاره می کند. در واقع، غنای مسول شبکه-جـریان ماورای این کاربردها می باشد. تئوری کلاسیک جریان شبکه، مـناطق متعدد و علی الظاهر نامرتبط بهینه سازی ترکیبی را به یکدیگر وصل می کند. تعادل ها، در بین قضیه 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
return flow f*
پیدا کردن مسیر افزایشیf –
بحث مسیر های افزایشیf – که منتهی به قضیه1-2 می شود مبنای استراتژی راس، برچسبی را در نتیجه فوردوفولکرسون فراهم می نماید که مسیر افزایشیf را پیدا می کند، زمانی که یک مسیر وجود دارد اساساً طرحواره برچسب زنی آنها درخت در حال رشد است(الگوریتم1-1-4). تصور این الگوریتم رشد درخت شبه مسیر ها است، که هر یک از منبعS شروع می شود. اگر جریان در هر قوس این شبه مسیرها کاهش یا افزایش یابد، بر اساس این که قوس پیشرو است یا پسرو، مسیر افزایشیf به محض اینکه مخزنt برچسب زنی شود، به دست می آید.
مرور از§4.1 : قوس مرزی قوسe است که از نقطه پایانی برچسب زده شدهV به نقطه پایانی برچسب نزدهW جـهت یابی شده است. بـرای ساخـتن و تـرسیم نمـودن مـسیر افـزایشیf، قـوس مـرزی e پسـرو می باشد(از راسW به راسV جهت یافته است) و می توان آن را به درخت اضافه نمود مادامیکه کمکی ∆e>0 داشته باشد.
اصطلاحات: در هر مرحله در حین رشد درخت یا ترسیم نمودن مسیر افزایشیf، فرض کنید کهe قوس مرزی درختt با نقطه پایانیVو w باشد. سپس گفته می شود که قوسeقابل استفاده است اگر، برای جریان جاریf یاe از راسV به راسW وf(e)<cap(e) جهت یافته باشدیاe از راسwبه راسVو f(e)>0 جهت یافته باشد.
نکته: بر اساس این طرح راس برچسب زنی، هر یک از مسیر های موجود افزایشیf به دست می آیند. اما بازدهی الگوریتم1-2 این است که در پیدا کردن مسیرهای خوب افزایشیf است. در واقع،فورد و فولکرسون نشان دادندکه اگر ظرفیت های قـوس اعداد مـبهمی باشند، سپس الگوریتـمی که از طرح برچسب زنی آنها استفاده می کند، محدود نمی شود. اما حتی زمانی که جریان ها و ظرفیت ها محدود به اعداد صحیح باشند، مسائلی در رابطه با بازدهی وجود دارند. برای مثال، اگر هر افزوده جریان که با جریان افزایش پیدا می کند، یک واحد باشد، پس تعداد افزایش های مورد نیاز برای بهینه سازی برابر با ظرفیت مینیمم قطع خواهد بود. چنین الگوریتمی بستگی به سایز ظرفیت های قوس خواهد داشت تا به سایز شبکه.
مثال4-2: برای شبکه نشان داده شده در شکل7-2، قوس از راسV به راسW گنجایش ظرفیت1 را دارد، در حالی که قوس های دیگر ظرفیتM دارند. اگر انتخاب مسیر افزایشی جریان در هر تکرار بین مسیر جهت دار<S,W,V,t> متناوب باشد، پس جریان در هر تکرار فقط یک واحد افزایش خواهد یافت. از این رو برای دست یافتن به ماکسیمم جریان باید2M تکرار داشته باشد.
ادموندز و کارپ از این مـسائل با الگوریتم ذیل اجتناب نـمودند، که تا حدودی طرح تعریف شده برچسب زنی فورد-فولکرسون است. این الگوریتم از تحقیقات اولیهbreadth برای پیدا کردن مسیر افزایشیf با حداقل تعداد قوس ها استفاده می کند. الگوریتم2-2 را به مسیر افزایشیf یا مینیمم قطع برمی گردد که نشان می دهد که جریان جاریf ماکسیمم جریان است.
Algorithm 2.2: Finding an Augmenting Path
Input: a flow f in an s-t network N
Output: an f-augmenting path Q or a minimum s-t cut with capacity val(f)
Initialize vertex set Vs:={s}
Write label 0 on vertex s
Initialize label counter I:=1
While vertex set Vs does not contain sink t
If ther are usable arcs
Let e be a usable arc whose labeled endpoint v
Has the smallest possible lable
Let w be the unlabeled endpoint of arc e
Set backpoint(w):=v
Vs:=VsU{w}
I:=I+1
Else
Return s-t cut <Vs,VN-Vs>
Reconstruct the f-augmenting path Q by following backpointers
Starting from sink t
Return f-augmenting path Q
Algorithm 2.3: FFEK 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]
Repeat
Apply algorithm 2.2 to 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
until an f*-augmenting path cannot be found in network N
return flow f*
مثال5-2: توالی اشکال ذیل الگوریتم3-2 را برای شبکه نمونه نشان داده شده، نشان می دهد که با جریان صفر شروع می شود. هر یک از سه شکل و رقم نخست جریان جاری را در شبکه و کوتاهترین مسیر افزایشیf (در تعداد قوس ها) را برای آن جریان نشان می دهد، که سپس برای دست یافتن به جریان نشان داده شده در شکل بعدی استفاده می شود. شکل نهایی مثال(شکل11-2) قطعs-t را با ظرفیت مسـاوی با جـریان جاری نشان می دهد و از این رهگذر بـهینه سـازی را اثبات می نماید.
توجه داشته باشید که در انتهای هر تکرار پایانی، قوس جهت یافته از منبعs به راسw و قوس جهت یافته از راسv به مخزنt قوس های مرزی درختT می باشند، اما قابل استفاده نیستند. این دو، قوس مـینیمم و قطع را به وجود می آورند<{s,x,y,z,v},{w,a,b,c,t}>. این مـوضوع قطعs-t را نشان می دهد که در اثبات قضیه3-2 شکل گرفته است.
نکته مـحاسبه ای: ادمـوندز و کارپ نشان می دهند که الگوریـتـم3-2 مـاکسیـمم جـریان را در کمـتر از
|EN|(|VN|+2)/2
افزایش نشان می دهد. چون محاسبه برای تحقیقbreadth-first، O(|EN|) است، نشان می دهد که محاسبه کلی الگوریتم3-2 است. O(|EN|²|VN|) الگوریتم های مفیدتری وجود دارند که به طور قابل توجهی پیچیده تر و خارج از حیطه این کتاب است.
1
22