درس سیزدهم: گراف دو بخشی یا Bipartite Graph

فرض کنيد در يک مجموعه آموزشی (مثلاً خانه رياضيات!) چندين کلاس آموزشی برای يک دوره چندروزه آماده شده باشد و تعدادی دانش پژوه قرار است در اين کلاس ها شرکت کنند. از آنجا که بعضی کلاسها همزمان هستند و همچنين هر دانش پژوه فقط تمايل به شرکت در بعضی کلاسها دارد جهت برنامه ريزی از هر دانش پژوه خواسته می شود کلاسهای مورد علاقه اش را اعلام کند. حال برای بررسی راحت تر اين موضوع    می توان از گرافها استفاده کرد بدين شکل که دو مجموعه رأس، يکی برای کلاسها و يکی برای دانش آموزان در نظر گرفت و رأس متناظر به هر دانش آموز را با يالهايي به کلاسهای مورد تقاضای او متصل کنيم. (بديهی است که در اين صورت هيچ يالی وجود ندارد که دو انتهايش اعضای يک مجموعه رأس باشد.)

در نظريه گرافها به چنين گرافهايي که مجموعه رئوس آن قابل افراز به دو مجموعه باشد و هر يال گراف يک رأس در هر مجموعه داشته باشد، گراف دوبخشی گفته می شود.

و یا

مساله اول

مسئله:(قضيه) ثابت كنيد يک گراف دو بخشی است اگر و فقط اگر دور با طول فرد نداشته باشد .

مساله دوم

مسئله: يک سالن مربعی شکل با طول ضلع صحيح و زوج داريم که در دو گوشه آن ستون قرار دارد و درون آن مانند شکل با مربع های 1 × 1 پوشانده شده است.

ه علت شکسته و فرسوده شدن موزاييک ها تصميم به تـعويض موزاييک ها گرفته شده است و برای اين کار از موزاييک های 2 × 1 نشکن استفاده می شود و هر موزاييک  2 × 1  جای دو موزاييک  1 × 1 قبلی قرار می گيرد.

آيا می توان فقط با اين نوع موزاييک های 2 × 1 کف همه سالن (به جز دو ستون) را فرش کرد؟(حل با گراف)