گراف دوبخشی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مثالی از يک گراف دو بخشی

گراف‌های دوبخشی به گراف‌هایی گفته می‌شوند که رأس‌ها به دو دسته مجزا قابل افراز هستند بگونه‌ای که تمامی یال‌های گراف بین گره‌های بین دو دسته مختلف باشند.

خواص مهم[ویرایش]

  • یک گراف دو بخشی است اگر و فقط اگر تمامی دورهای از طول زوج باشند. بنابراین به عنوان مثال یک گراف دو بخشی نمی‌تواند شامل یک گراف کامل با ۳ رأس باشد.
  • یک گراف دو بخشی است اگر و فقط اگر ۲-رنگ پذیر باشد.

جستارهای وابسته[ویرایش]

پیوند به بیرون[ویرایش]