گراف انتساب شغل

الگو:میان‌ویکی-نیاز الگو:بدون منبع گراف انتساب مشاغل( به انگلیسی:job assignments) نوعی از گراف دوبخشی است.

فرض کنید در یک گروه ، m کارمند و j شغل مختلف داریم که باید انجام شوند که $m\le j$. هر کارمند برای انجام یک یا بیشتر از این j شغل، آموزش دیده است. میتوانیم از یک گراف برای مدل کردن تواناییهای کارمندان استفاده کنیم. هر کارمند و هر شغل را با یک رأس نمایش میدهیم. برای هر کارمند، یالی از رأس نمایش دهنده آن، به تمام رئوسی که نمایش دهنده شغلهایی هستند که این کارمند برای آن‌ها آموزش دیده است، رسم میکنیم. توجه کنید که مجموعه رئوس این گراف را می‌توان به دو مجموعه مجزا افراز کرد، مجموعه رئوس نمایش دهنده کارمندان و مجموعه رئوس نمایش دهنده مشاغل و هر یال، رأس نمایش دهنده یک کارمند را به رأس نمایش دهنده یک شغل متصل می‌کند. در نتیجه، این گراف دو قسمتی است.

مثال

فرض کنید که گروهی دارای چهار کارمند است: آیدین، بهنام، یاشار و داوود؛ و فرض کنید که برای تکمیل یک پروژه، چهار شغل: شناسایی نیازها، معماری، پیاده‌سازی و تست باید انجام شوند. فرض کنید که آیدین برای مشاغل شناسایی نیازها و تست، آموزش دیده است؛ بهنام برای معماری، پیاده‌سازی و تست، آموزش دیده است؛ یاشار برای شناسایی نیازها، معماری و پیاده‌سازی، آموزش دیده است و داوود فقط برای شناسایی نیازها آموزش دیده است. تواناییهای این کارمندان را می‌توان با گراف دوقسمتی نشان داده شده در شکل زیر مدل کرد.

برای تکمیل پروژه، باید شغلها را به کارمندان به گونهای نسبت دهیم که برای هر شغل، کارمندی در نظر گرفته شود و به هیچ کارمندی، بیش از یک شغل اختصاص داده نشود. در این مورد همان طور که در شکل زیر نشان داده شده‌است، میتوانیم به آیدین شغل تست، به بهنام شغل پیاده‌سازی، به یاشار شغل معماری و به داوود شغل شناسایی نیازها را اختصاص دهیم.

مدل کردن شغل ها

یافتن یک انتساب مشاغل به کارمندان را می‌توان به صورت یافتن یک انطباق در مدل گراف تصور کرد. یک انطباق در یک گراف ساده، زیرمجموعه‌ای از مجموعه یالهای گراف است به طوری که هیچ دو یالی با یک رأس یکسان، متلاقی نباشند؛ انطباق ماکزیمم، انطباقی است که دارای بیشترین تعداد یال است. به عبارت دیگر، یک انطباق، زیرمجموعه‌ای از یالهاست به گونهای که اگر {u, v} و {s, t} یالهای این انطباق باشند، آنگاه v و u ، t ، s مجزا هستند. برای انتساب مشاغل به کارمندان به طوری که برای بیشترین تعداد کارمندان، شغل در نظر گرفته شود، در گراف مدل کننده تواناییهای کارمندان، به دنبال یک انطباق ماکزیمم میگردیم.