بخشی از مقاله

جريانها و كاربردهاي شبكه

ـ جريانها و قطع ها در شبكه
ـ حل نمودن مسأله جريان ماكزيمم
ـ تعيين نمودن همبندي نمودار
ـ تطابق ها، خطوط مورب و پوشش هاي رأسي

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

در متن اصلی مقاله به هم ریختگی وجود ندارد. برای مطالعه بیشتر مقاله آن را خریداری کنید