گراف دو بخشی (Bipartite Graph)، در ریاضیات (Mathematics)

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

گراف دو بخشی (Bipartite Graph) :

گراف دوبخشی گرافی است که می توان رئوس آن را به دو مجموعه مجزا و مستقل مانند U و V تقسیم کرد به طوری که هر یال گراف، یک راس از مجموعه U را به یک راس از مجموعه V متصل کند و هیچ یالی بین رئوس داخل یک مجموعه وجود نداشته باشد. به عبارت ساده تر، می توان آن را به صورت دو دسته از گره ها تصور کرد که اتصالات فقط بین این دو دسته برقرار است. یک مثال کلاسیک، رابطه بین کارگران و کارهایی است که می توانند انجام دهند. هر کارگر با یال هایی به کارهایی که مهارت انجامش را دارد متصل می شود. گراف های دوبخشی در مسائل تطابق (Matching)، مانند یافتن بهترین تخصیص کار به کارگران، کاربرد فراوانی دارند.