مقاله ها

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

تعریف

گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه‌ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می‌نامند.

  • یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنها برابر مجموعه A باشد. و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که: X\bigcupY = V و X\bigcapY = \varnothing
  • مثال

به عنوان مثال گراف زیر یک گراف دو بخشی است:


ضمنا در مورد گرافهای هامنی این مطلب را ببینبید.

 

مثالی از يک گراف دو بخشی

 

تاریخ

طراحی سایت
سه شنبه 23 مرداد 1397.
امروز
Aug 14 2018.
مطابق با:

ورود به سایت

یک حدیث

امام حسن (سلام الله علیه) : مَن عَرَفَ اللَّهَ أحَبَّهُ. هر كس خدا را بشناسد، دوستش بدارد. دوستی در قرآن وحدیث: ص414 – ح 963

خبرخوان

 

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