مقاله ها

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

گراف دو بخشی 

مفهوم شهودی

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

 

تاریخ

طراحی سایت
دوشنبه 30 مهر 1397.
امروز
Oct 22 2018.
مطابق با:

ورود به سایت

یک حدیث

امام مهدی (سلام الله علیه) : أكثِرُوا الدُّعاءَ بِتَعجيلِ الفَرَجِ فَإِنَّ ذلِكَ فَرَجُكُم. براى تعجيل در فرج بسيار دعا كنيد، كه مايه گشايش در كار شما است. كمال الدّين - ص 485

خبرخوان

 

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