گراف دو بخشی:
مفهوم شهودی:
فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده اند. حال این سوال مطرح می شود که آیا می توان به هر متقاضی شغلی متناسب او اختصاص داد؟
برای حل چنین مسئله ای که به مسئله ی تخصیص موسوم است، با استفاده از
گراف می توان وضعیت های خاص را پیاده سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه ای به نام
X و مجموعه مشاغل بدون متصدی را در مجموعه ای به نام
Y قرار می دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه
X یک یا چند عضو از مجموعه
Y توسط یال ها وصل می نماید.
به عبارت دیگر گراف بوجود امدی دارای یالهای
xy است که مر متقاضی
x را از مجموعه
X به شغلهای مناسب
y از مجموعه
Y متصل می نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه
X(متفاضیان) یا هیچ دو راس متعلق به مجموعه
Y(مشاغل) توسط هیچ یالی به هم متصل نمی باشند. چنین گرافی را
گراف دوبخشی یا
دوپارچه می گویند.
تعریف گراف دوبخشی:
گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می نامند.
- یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنها برابر مجموعه A باشد. و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که:
به عنوان مثال گراف زیر یک گراف دو بخشی است:
چرا که در این گراف مجموعه رئوس را می توان به دو مجموعه
و
چنان افراز نمود که هیچ دو راسی در این دو مجموعه با هم مجاور نباشند و هر یال تنها یک انتها در مجموعه اول و یک انتها در مجموعه دوم داشته باشد.
- قضیه: اگر گراف k-منتظم، دارای دوبخش X و Y باشد، آنگاه تعداد عناصر X و Y باهم برابر است.
برهان:
فرض می کنیم X دارای m راس و Y دارای n راس از راسهای گراف دو بخشی k-منتظم می باشد. یشان می دهیم که: m=n.
از هر راس در مجموعه X به تعداد k، یال خارج می شود(چرا؟) پس تعداد کل یالها(q) برابر است با: q=km
چون جمعا" m+n راس داریم، لذا مطابق قضیه مجموع درجه های راس ها و تعریف گراف k-منتظم داریم:
پس:
و لذا حکم برقرار است.
گراف دو بخشی کامل:
گراف دو بخشی کامل یک گراف دو بخشی است که مجموع رئوس آن به دو مجموعه X و Y چنان افراز شده است و هر راس در ان به هر راس وصل شده است. گراف دو بخشی کامل را با نماد نشان می دهند که در آن m تعداد عناصر مجموعه X و n تعداد عناصر مجموعه Y است.
- به عنوان مثال گراف زیر یک گراف دو بخشی کامل است.
- قضیه: در گراف دو بخشی کامل همواره داریم: که در آن q اندازه گراف مذکور است.
برهان:
می دانیم گراف دارای m راس در یک مجموعه و n راس در مجموعه ای دیگر است.
تعداد کل راس ها P=m+n می باشد(مرتبه گراف). اما برای یافتن تعداد یالهای گراف دو بخشی کامل ابتدا تعداد کل یالهای یک گراف کامل از مرتبه P=m+n را محاسبه کرده سپس تعداد کل یالهایی که راس های دو مجموعه را در خود دو مجموعه به هم وصل می کند از آن کم می کنیم. داریم:
- قضیه: اگر G یک گراف ساده و دو بخشی از مرتبه p و اندازه q باشد آنگاه:
همچنین ببینید: