دانلود با لینک مستقیم و پر سرعت .
لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل: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 جهت یافته است.
نکتـه: مـثال ها و کاربــردها در کل ایـن فصل مــستلزم شـبـکه هایی با گنجـایـش های اعــداد صـحیح می باشند که توضیح آن را آسان می سازد. هیچ استلزام زیادی وجود ندارد اگر ظرفیت ها اعداد گویای غیر اعداد صحیح باشند. چنین شبکه ای را می توان در یک شبکه هم ارز منتقل نمود که گنجایش های آن اعـداد صحیح به واسطه ضرب نمودن هر گنـجایش در آخریـن مضرب مـشترک مخرج های گنجایـش ها می باشند.
