مقاله ها

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

گراف دو بخشی 

مفهوم شهودی

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

 

تاریخ

طراحی سایت
جمعه 26 مرداد 1397.
امروز
Aug 17 2018.
مطابق با:

ورود به سایت

یک حدیث

حضرت محمد صلى الله عليه و آله و سلّم : إنَّ العبدَ لَيَرفَعُ يَدَهُ إلى اللّه ومَطعَمُهُ حَرامٌ ، فكيفَ يُستَجابُ لَهُ وهذا حالُهُ ؟! همانا بنده دستش را (براى دعا) به درگاه خدا بالا مىبرد در حالى كه خوراكش حرام است ؛ با چنين حالى ، چگونه دعايش مستجاب شود ؟. إرشاد القلوب : 149 منتخب ميزان الحكمة : 196

خبرخوان

 

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