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