![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/langfa-640px-Simple-bipartite-graph.svg.png&w=640&q=50)
گراف دوبخشی
From Wikipedia, the free encyclopedia
در نظریهٔ گراف (یکی از شاخههای ریاضیات)، گراف دوبخشی گرافی است که راسهایش را میتوان به دو مجموعهٔ مجزا مثل و
تقسیم کرد، طوری که هر یال از آن گراف، یک راس از
را به یک راس از
متصل میکند. معادلا، گراف دوبخشی گرافی است که دور به طول فرد ندارد.
![]() |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/320px-Simple-bipartite-graph.svg.png)
میتوان به و
به چشم یک رنگآمیزی مجاز گراف نگاه کرد: اگر همهٔ راسهای مجموعهٔ
را آبی و همهٔ راسهای مجموعهٔ
را سبز کنیم، دو راس انتهایی هر یال رنگهای متفاوتی خواهند داشت که نشاندهندهٔ یک رنگآمیزی مجاز برای گراف است. از طرف دیگر، این نوع رنگآمیزی برای گرافهای غیر دوبخشی (مثل مثلث) غیرممکن است. مثلاً در مثلث، اگر یک راس را به رنگ آبی و دیگری را به رنگ سبز درآوریم، راس سوم را نمیتوانیم با هیچکدام از این رنگها رنگ کنیم، چون این راس به هر دو راس دیگر متصل است.
گراف دو بخشی را معمولاً به صورت نشان میدهیم که
و
دو بخش گراف و
مجموعهٔ یالهای گراف است. اگر یک گراف دوبخشی همبند نباشد، ممکن است بتوان راسهای آن را به شیوههای مختلف به دو بخش تقسیم نمود (یعنی ممکن است
و
یکتا نباشند). در این صورت نمایش
سودمند واقع میشود؛ چون به کمک آن میتوان یک حالت خاص تقسیم رئوس گراف به دو بخش را از بقیهٔ حالات متمایز کرد. اگر
، گراف
را گراف دوبخشی متوازن مینامیم. اگر درجهٔ تمام راسهای
با هم و نیز درجهٔ تمام راسهای
با هم برابر باشد، گراف
را گراف دوبخشی شبه منتظم مینامیم.