مقاله شبکه ها و تطابق در گراف

اختصاصی از نیک فایل مقاله شبکه ها و تطابق در گراف دانلود با لینک مستقیم و پر سرعت .

تعداد صفحات : 50

فرمت فایل : word (قابل ویرایش)

فهرست مطالب :

عنوان

مقدمه

فصل 1

شبکه ها

1-1 شارش ها

1-2 برش ها

1-3 قضیه شارش ماکزیمم – برش مینیمم

1-4 قضیه منجر

فصل 2

تطابق ها

2-1 انطباق ها

2-2 تطابق ها و پوشش ها در گراف های دو بخش

2-3 تطابق کامل

2-4 مسأله تخصبص شغل

تعریف 1-1 فرض کنیم N=(V,E) یک گراف سودار همبند بیطوقه باشد. N را یک شبکه یا یک شبکه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:

(الف) رأس یکتایی مانند  وجود دارد به طوری که ، یعنی درجة ورودی a، برابر 0 است. این رأس a را مبدأ یا منبع می‌نامند.

(ب) رأس یکتایی مانند  به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجة خروجی z، برابر با 0 است.

تعریف 1-2 فرض کنیم  یک شبکة حمل و نقل باشد تابع f از E در N، یعنی مجموعة اعداد صحیح نامنفی، را یک شارش برای N می نامند هرگاه

الف) به ازای هر کمان  و

ب) به ازای هر ، غیر از مبدأ a یا مقصد  z ،  (اگر کمانی مانند (v,w) وجود نداشته باشد، قرار می دهیم

تعریف 1-5 برش C در N، یک برش مینیمم است، اگر هیچ برش دیگری مانند  در N با شرط  وجود نداشته باشد.

اگر  یک شارش ماکزیمم و  یک برش مینیمم به عنوان حالت خاصی از قضیه 1-1

داریم:   (1-4)            

1-3 قضیه شارش ماکزیمم – برش مینیمم

در این بخش الگوریتمی برای تعیین یک شارش ماکزیمم در شبکه ها ارائه می‌نمائیم. یکی از اساسی‌ترین ملزومات چنین الگوریتمی این است که در صورت دیدن یک شارش، بتواند تشخیص دهد آیا این شارش ماکزیمم هست یا خیر. بنابراین در شروع کار، نگاهی به این مسأله می‌اندازیم.

  

فرض کنید f یک شارش در شبکه N باشد. به هر مسیر S در N، یک عدد صحیح نامنفی l(S) به صورت روبرو نسب می‌دهیم:

اگر t یک کمان رو به جلو از S باشد.

اگر t یک کمان معکوس از S باشد.

 

که در آن:

شارش اصلاح شده بر پایة S می ‌خوانیم.

در شکل 1-4 (ب) شارش اصلاح شده شبکه 1-4 (الف) بر پایه مسیر -f افزایشی  نشان داده شده است.

شکل 1-4 (الف) مسیر -f افزایشی S (ب) شارش اصلاح شده بر پایه f

در شکل (الف)

در شکل (ب)