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

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

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

فهرست مطالب

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

شبكه ها

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 (ب) در هر دو شرط صدق می كند و بنابراین، شارشی برای شبكهء مفروض است.

توجه داشته باشید كه هر شبكه، حداقل دارای یك شارش است، زیرا تابع fای كه در آن به ازای هر  داشته باشیم:  در هر دو شرط تعریف
1-2 صدق می كند. این تابع، شارش صفر نامیده می شود.

تعریف 1-3 فرض كنیم f شارشی برای شبكة حمل و نقل N=(V,E) باشد.

الف) كمانی مانند e متعلق به این شبكه را اشباع شده می نامند هر گروه f(e)=c(e) اگر f(e)<c(e) این كمان را اشباع نشده می نامند.

ب) اگر a مبدأ N باشد،  را مقدار شارش می نامند.

مثال 1-3 در شبكه شكل 1-2 (ب) فقط كمان  اشباع شده است. هر یك از كمان‌های دیگر اشباع نشده است. مقدار شارش این شبكه

 

است. ولی آیا شارش دیگری مانند  وجود دارد كه به ؟

می‌گوئیم شارش fدر N، یك شارش ماكزیمم  است، هر گاه هیچ شارش دیگری مانند  در N با شرط  وجود نداشته باشد.

هدف ما در ادامه، تعیین یك شارش ماكزیمم است. برای انجام این كار، ملاحظه می‌كنیم كه در شكل 1-2 (ب) داریم.

 

درنتیجه، شارش كل خارج شده از مبدأ a شارش كل وارد شده به مقصد z برابر  است.

نكته اخیر در مثال 1-3 شرط معقولی به نظر می‌رسد، ولی آیا در حالت كلی چنین وضعیتی روی می دهد؟ برای اثبات آن در مورد هر شبكه دلخواه به نوع خاصی از مجموعه های برشی كه در قسمت بعد می‌آید، نیاز داریم.

1-2          برش ها

تعریف 1-4 اگر  یك شبكهء حمل و نقل و C یك مجموعة برشی برای گراف بیسوی وابسته به N به صورت  كه در آن  باشد، C را یك برش یا یك برش a-z می نامند هرگاه حذف كمانهای C از شبكة مفروض به جدایی a و z منتهی شود.

ظرفیت هر برش، كه با capC نشان داده می شود، با

(1-1)                                                           

یعنی مجموع ظرفیتهای همة كمانهای (y,w) كه در آن  و ، تعریف می‌شود.