مقاله ها

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

تعریف

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

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

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


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

 

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

 

تاریخ

طراحی سایت
شنبه 5 خرداد 1397.
امروز
May 26 2018.
مطابق با:

ورود به سایت

یک حدیث

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

خبرخوان

 

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