گراف دوبخشی

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

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

خواص مهم

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

جستارهای وابسته

• گراف کامل دو بخشی

پیوند به بیرون

• خبرگاه المپیاد کامپیوتر