شبكه ها و تطابق در گراف

شبكه های حمل و نقل، واسطه‌هایی برای فرستادن كالاها از مراكز تولید به فروشگاهها هستند این شبكه ها را می‌توان به صورت یك گراف جهت دار با یك سری ساختارهای اضافی درنظر گرفت و آن ها را به صورت كارآیی مورد تحلیل و بررسی قرار داد

شبكه ها و تطابق در گراف


شبكه ها
1-1 شارش ها
شبكه های حمل و نقل، واسطه‌هایی برای فرستادن كالاها از مراكز تولید به فروشگاهها هستند. این شبكه ها را می‌توان به صورت یك گراف جهت دار با یك سری ساختارهای اضافی درنظر گرفت و آن ها را به صورت كارآیی مورد تحلیل و بررسی قرار داد. این گونه گراف های جهت دار، نظریه ای را به وجود آورده اند كه موضوع مورد بحث ما در این فصل می باشد. این نظریه ابعاد وسیعی از كاربردها را دربرمی‌گیرد.
تعریف 1-1 فرض كنیم N=(V,E) یك گراف سودار همبند بیطوقه باشد. N را یك شبكه یا یك شبكه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:
(الف) رأس یكتایی مانند وجود دارد به طوری كه ، یعنی درجة ورودی a، برابر 0 است. این رأس a را مبدأ یا منبع می‌نامند.
(ب) رأس یكتایی مانند به نام مقصد یا چاهك، وجود دارد به طوری كه od(z)، یعنی درجة خروجی z، برابر با 0 است.
(پ) گراف N وزندار است و از این رو، تابعی از E در N، یعنی مجموعة اعداد صحیح نامنفی، وجود دارد كه به هر كمان یك ظرفیت، كه با نشان داده می‌شود، نسبت می‌دهد.
برای نشان دادن یك شبكه، ابتدا گراف جهت زمینه آن (D) را رسم كرده و سپس ظرفیت هر كمان را به عنوان برچسب آن كمان قرار می‌دهیم.
مثال 1-1 گراف شكل 1-1 یك شبكه حمل و نقل است. در این جا رأس a مبدأ و راس z مقصد است و ظرفیتها، كنار هر كمان نشان داده شده‌اند. چون ، مقدار كالای حمل شده از a به z نمی‌تواند از 12 بیشتر شود. با توجه به بازهم این مقدار محدودتر می‌شود و نمی‌تواند از 11 تجاوز كند. برای تعیین مقدار ماكسیممی كه می‌توان از a به z حمل كرد باید ظرفیتهای همة كمانهای بشكه را درنظر بگیریم.

تعریف 1-2 فرض كنیم یك شبكة حمل و نقل باشد تابع f از E در N، یعنی مجموعة اعداد صحیح نامنفی، را یك شارش برای N می نامند هرگاه
الف) به ازای هر كمان و
ب) به ازای هر ، غیر از مبدأ a یا مقصد z ، (اگر كمانی مانند (v,w) وجود نداشته باشد، قرار می دهیم
مقدار تابع f برای كمان e، f(e) را می توان به نرخ انتقال داده در طول e، تحت شارش f تشبیه كرد. شرط اول این تعریف مشخص می‌كند كه مقدار كالای حمل شده در طول هر كمان نمی تواند از ظرفیت آن كمان تجاوز كند، كران بالایی شرط الف را قید ظرفیت می‌نامند.
شرط دوم، شرط بقا نامیده می شود و ایجاب می كند كه، مقدار كالایی كه وارد رأس مانند v می شود با مقدار كالایی كه از این رأس خارج می شود برابر باشد. این امر در مورد همة رأسها به استثنای مبدأ و مقصد بر قرار است.
مثال 1-2 در شبكه های شكل 1-2، نشان x,y روی كمانی مانند e به این ترتیب تعیین شده است كه y , x=c(e) مقداری است كه شارشی مانند f به این كمان نسبت داده است. نشان هر كمان مانند e در صدق می كند. در شكل 1-2 (الف)، شارش، وارد رأس می شود،5 است، ولی شارشی كه از آن رأس خارج می شود 4=2+2 است. بنابراین، در این حالت تابع f نمی تواند یك شارش باشد. تابع f برای شكل 1-2 (ب) در هر دو شرط صدق می كند و بنابراین، شارشی برای شبكهء مفروض است.

فهرست مطالب
مقدمه
فصل 1
شبكه ها
1-1 شارش ها
1-2 برش ها
1-3 قضیه شارش ماكزیمم – برش مینیمم
1-4 قضیه منجر

فصل 2
تطابق ها
2-1 انطباق ها
2-2 تطابق ها و پوشش ها در گراف های دو بخش
2-3 تطابق كامل
2-4 مسأله تخصیص شغل

منابع

برچسب ها : شبكه ها و تطابق در گراف , شبكه , تطابق , گراف , شبكه ها و تطابق در گراف , مقاله , پژوهش , تحقیق , پروژه , دانلود مقاله , دانلود پژوهش , دانلود تحقیق , دانلود پروژه