گراف دو بخشی (Bipartite Graph)، در ریاضیات (Mathematics)
انواع گراف ساده (Simple Graph) را در آموزش زیر شرح دادیم :
گراف دو بخشی (Bipartite Graph) :
گراف دو بخشی گرافی است که مجموعه رأس های آن را می توان به دو مجموعه مجزا و ناتهی
\[ U \]و
\[ V \]افراز (Partition) کرد، به طوری که هر یال از گراف، یک رأس از مجموعه
\[ U \]را به یک رأس از مجموعه
\[ V \]متصل کند و هیچ یالی بین دو رأس درون یک مجموعه وجود نداشته باشد. به عبارت دیگر، رأس های هم مجموعه مجاور (Adjacent) یکدیگر نیستند. این گراف ها کاربردهای فراوانی دارند، از جمله در مسئله های تطابق (Matching)، شبکه های حمل و نقل و مدل سازی روابط دودویی (مانند رابطه کارگران و مشاغل). یک ویژگی مهم گراف های دو بخشی این است که هیچ دور فرد (Odd Cycle) ندارند؛ یعنی طول تمام دورهای موجود در آن (اگر دوری وجود داشته باشد) زوج است. حالت خاصی از این گراف، گراف دو بخشی کامل (Complete Bipartite Graph) است که با نماد
\[ K_{m,n} \]نمایش داده می شود و در آن هر رأس از مجموعه اول (
\[ m \]رأس) به تمام رأس های مجموعه دوم (
\[ n \]رأس) متصل است. گراف ستاره ای (
\[ K_{1,n-1} \]) مثالی از یک گراف دو بخشی کامل است.
\[ K_{m,n} \]