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

گراف انتساب مشاغل ( به انگلیسی:job assignments ) نوعی از گراف دوبخشی است.
فرض کنید در یک گروه ، m کارمند و j شغل مختلف داریم که باید انجام شوند که m ≤ j . هر کارمند برای انجام یک یا بیشتر از این j شغل، آموزش دیده است. میتوانیم از یک گراف برای مدل کردن تواناییهای کارمندان استفاده کنیم. هر کارمند و هر شغل را با یک رأس نمایش میدهیم. برای هر کارمند، یالی از رأس نمایش دهنده آن، به تمام رئوسی که نمایش دهنده شغلهایی هستند که این کارمند برای آن ها آموزش دیده است، رسم میکنیم. توجه کنید که مجموعه رئوس این گراف را می توان به دو مجموعه مجزا افراز کرد، مجموعه رئوس نمایش دهنده کارمندان و مجموعه رئوس نمایش دهنده مشاغل و هر یال، رأس نمایش دهنده یک کارمند را به رأس نمایش دهنده یک شغل متصل می کند. در نتیجه، این گراف دو قسمتی است.
فرض کنید که گروهی دارای چهار کارمند است: آیدین، بهنام، یاشار و داوود؛ و فرض کنید که برای تکمیل یک پروژه، چهار شغل: شناسایی نیازها، معماری، پیاده سازی و تست باید انجام شوند. فرض کنید که آیدین برای مشاغل شناسایی نیازها و تست، آموزش دیده است؛ بهنام برای معماری، پیاده سازی و تست، آموزش دیده است؛ یاشار برای شناسایی نیازها، معماری و پیاده سازی، آموزش دیده است و داوود فقط برای شناسایی نیازها آموزش دیده است. تواناییهای این کارمندان را می توان با گراف دوقسمتی نشان داده شده در شکل زیر مدل کرد.
برای تکمیل پروژه، باید شغلها را به کارمندان به گونهای نسبت دهیم که برای هر شغل، کارمندی در نظر گرفته شود و به هیچ کارمندی، بیش از یک شغل اختصاص داده نشود. در این مورد همان طور که در شکل زیر نشان داده شده است، میتوانیم به آیدین شغل تست، به بهنام شغل پیاده سازی، به یاشار شغل معماری و به داوود شغل شناسایی نیازها را اختصاص دهیم.
یافتن یک انتساب مشاغل به کارمندان را می توان به صورت یافتن یک انطباق در مدل گراف تصور کرد. یک انطباق در یک گراف ساده، زیرمجموعه ای از مجموعه یالهای گراف است به طوری که هیچ دو یالی با یک رأس یکسان، متلاقی نباشند؛ انطباق ماکزیمم، انطباقی است که دارای بیشترین تعداد یال است. به عبارت دیگر، یک انطباق، زیرمجموعه ای از یالهاست به گونهای که اگر {u, v} و {s, t} یالهای این انطباق باشند، آنگاه v و u ، t ، s مجزا هستند. برای انتساب مشاغل به کارمندان به طوری که برای بیشترین تعداد کارمندان، شغل در نظر گرفته شود، در گراف مدل کننده تواناییهای کارمندان، به دنبال یک انطباق ماکزیمم میگردیم.