مقاله ها

گرافهای دوبخشی

گراف دو بخشی 

مفهوم شهودی

فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می‌باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده‌اند. حال این سوال مطرح می‌شود که آیا می‌توان به هر متقاضی شغلی متناسب او اختصاص داد؟ برای حل چنین مسئله‌ای که به مسئلهٔ تخصیص موسوم است، با استفاده از گراف می‌توان وضعیت‌های خاص را پیاده سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه‌ای به نام X و مجموعه مشاغل بدون متصدی را در مجموعه‌ای به نام Y قرار می‌دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یال‌ها وصل می‌نماید. به عبارت دیگر گراف بوجود امدی دارای یالهای xy است که مر متقاضی x را از مجموعه X به شغلهای مناسب y از مجموعه Y متصل می‌نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X (متفاضیان) یا هیچ دو راس متعلق به مجموعه Y (مشاغل) توسط هیچ یالی به هم متصل نمی‌باشند. چنین گرافی را گراف دوبخشی یا دوپارچه می‌گویند.

 

تاریخ

طراحی سایت
پنجشنبه 3 خرداد 1397.
امروز
May 24 2018.
مطابق با:

ورود به سایت

یک حدیث

حضرت مهدی (علیه السلام) ما أرْغَمُ أنْفُ الشَيْطانَ بِشَىءٍ مِثْلَ الصَّلاةِ، فَصَلِّها وَ أرْ غَمْ أنْفَ الشَّيْطانَ؛ با هيچ چيز مثل نماز، بينى شيطان به خاك ماليده نمى شود پس نماز را به پادار و بينى شيطان را به خاك بمال. بحارالانوار، ج 53، ص 182

خبرخوان

 

شما اینجا هستید: صفحه ی اصلی