گراف های بدون دور فرد (Graphs with No Odd Cycles)، در ریاضیات (Mathematics)

انواع گراف دو بخشی (Bipartite Graph) را در آموزش زیر شرح دادیم :

گراف های بدون دور فرد (Graphs with No Odd Cycles) :

این دسته یک توصیف کلی تر از تمام گراف های دوبخشی است. در حقیقت، تعریف نظری گراف دوبخشی این است: یک گراف دو بخشی است اگر و تنها اگر شامل هیچ دور فردی (Odd Cycle) به عنوان زیرگراف نباشد . این قضیه، که یک ویژگی ساختاری عمیق است، به عنوان یک روش آزمون برای دوبخشی بودن گراف ها به کار می رود.

به عبارت دیگر، هر گرافی که فاقد هرگونه دور به طول فرد (3، 5، 7 و ...) باشد، به طور خودکار یک گراف دوبخشی محسوب می شود. این ویژگی مستقل از این است که گراف شامل دورهای زوج باشد یا خیر. این تعریف هم ارز با مفهوم 2-رنگ پذیری (2-Colorability) گراف ها است .