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

لینک دریافت فایل خرید پایین توضیحات

دسته بندی : وورد

نوع فایل :  .Doc ( قابل ویرایش اماده پرینت )

تعداد : 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}>