گراف دوبخشی

در نظریهٔ گراف (یکی از شاخه های ریاضیات)، گراف دوبخشی گرافی است که راس هایش را می توان به دو مجموعهٔ مجزا مثل U {\displaystyle U} و V {\displaystyle V} تقسیم کرد، طوری که هر یال از آن گراف، یک راس از U {\displaystyle U} را به یک راس از V {\displaystyle V} متصل می کند. معادلا، گراف دوبخشی گرافی است که دور به طول فرد ندارد.
هر درخت دوبخشی است.
دور به طول زوج دوبخشی است.
هر گراف مسطح که طول تمام وجه هایش زوج است، دوبخشی می باشد. حالت های خاص این مورد، گراف های شبکه ای (grid graph) و گراف های مربعی (squaregraph) هستند که در آن ها هر وجه داخلی ۴ یال دارد و هر راس داخلی ۴ یا تعداد بیشتری همسایه دارد.
گراف کامل دوبخشی که از دو بخش با تعداد راس های m {\displaystyle m}   و n {\displaystyle n}   تشکیل شده است و با Km,n نمایش داده می شود، گراف دوبخشی G = ( U , V , E ) {\displaystyle G=(U,V,E)}   است که U {\displaystyle U}   و V {\displaystyle V}   مجموعه های متمایز از راس های گراف، به ترتیب با اندازه های m {\displaystyle m}   و n {\displaystyle n}   هستند و E {\displaystyle E}   هر راس از U {\displaystyle U}   را به تمام راس های V {\displaystyle V}   وصل می کند. پس نتیجه می شود که Km,n، m n {\displaystyle mn}   یال دارد. گراف های تاجی شکل (crown graph) ارتباط نزدیکی با گراف های کامل دوبخشی دارند و در واقع با حذف یال های یک تطابق کامل از گراف کامل دوبخشی به دست می آیند.
گراف های k-مکعب، partial cube و گراف های میانه (median graphs) دوبخشی هستند. در این گراف ها، راس ها را می توان با رشته هایی از ۰ و ۱ به طول برابر برچسب گختلاف داشته باشند. یک روش تقسیم رئوس این گونه گراف ها به دوبخش، به این صورت است که رئوسی را که تعداد یک های موجود در رشتهٔ متناظر با آن ها فرد است، در یک دسته و رئوسی را که تعداد یک های موجود در رشتهٔ متناظر با آن ها زوج است، در دسته ای دیگر قرار می دهیم. درخت ها و گراف های مربعی (squaregraphs) نوعی از گراف های میانه ای (median graphs) هستند و هر گراف میانه ای (median graph) یک partial cube است.
می توان به U {\displaystyle U} و V {\displaystyle V} به چشم یک رنگ آمیزی مجاز گراف نگاه کرد: اگر همهٔ راس های مجموعهٔ U {\displaystyle U} را آبی و همهٔ راس های مجموعهٔ V {\displaystyle V} را سبز کنیم، دو راس انتهایی هر یال رنگ های متفاوتی خواهند داشت که نشان دهندهٔ یک رنگ آمیزی مجاز برای گراف است. از طرف دیگر، این نوع رنگ آمیزی برای گراف های غیر دوبخشی (مثل مثلث) غیرممکن است. مثلاً در مثلث، اگر یک راس را به رنگ آبی و دیگری را به رنگ سبز درآوریم، راس سوم را نمی توانیم با هیچ کدام از این رنگ ها رنگ کنیم، چون این راس به هر دو راس دیگر متصل است.
گراف دو بخشی را معمولاً به صورت G = ( U , V , E ) {\displaystyle G=(U,V,E)} نشان می دهیم که U {\displaystyle U} و V {\displaystyle V} دو بخش گراف و E {\displaystyle E} مجموعهٔ یال های گراف است. اگر یک گراف دوبخشی همبند نباشد، ممکن است بتوان راس های آن را به شیوه های مختلف به دو بخش تقسیم نمود (یعنی ممکن است U {\displaystyle U} و V {\displaystyle V} یکتا نباشند). در این صورت نمایش G = ( U , V , E ) {\displaystyle G=(U,V,E)} سودمند واقع می شود؛ چون به کمک آن می توان یک حالت خاص تقسیم رئوس گراف به دو بخش را از بقیهٔ حالات متمایز کرد. اگر | U | = | V | {\displaystyle |U|=|V|} ، گراف G {\displaystyle G} را گراف دوبخشی متوازن می نامیم. اگر درجهٔ تمام راس های U {\displaystyle U} با هم و نیز درجهٔ تمام راس های V {\displaystyle V} با هم برابر باشد، گراف G {\displaystyle G} را گراف دوبخشی شبه منتظم می نامیم.
وقتی رابطهٔ بین دو گروه مختلف از اشیا را مدل سازی می کنیم، معمولاً گراف های دوبخشی به طور طبیعی ظاهر می شوند. به عنوان مثال، فرض کنید یک گراف داشته باشیم که راس های آن نمایانگر بازیکنان فوتبال و باشگاه ها باشند. یک بازیکن را به یک باشگاه وصل می کنیم، اگر آن بازیکن برای آن باشگاه بازی کرده باشد. این گراف نمونه ای از شبکه های وابستگی (affiliation network) است. این شبکه ها نوعی گراف دوبخشی هستند و از آن ها در آنالیز شبکهٔ اجتماعی (social network analysis) استفاده می شود.