این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.
اگر راس های گراف به دو مجموعه افراز گردند. به طوری که هنگام رسم گراف، هیچ یالی بین راس های مجموعه ی رسم نگردد و هیچ یالی بین راس های مجموعه ی نیز ترسیم نشود، گراف را یک گراف دو بخشی نامیم.
اگر دارای عضو و دارای عضو باشد، آنگاه گرافی که هر راس درون را به همه ی راس های وصل کرده باشد را گراف دو بخشی کامل نامیده و با نشان می دهیم.
گراف دو بخشی است اگر و تنها اگر دارای هیچ دوری به طول فرد نباشد.
اثبات اگر دو بخشی باشد آنگاه اثبات این که هر دور در به طول زوج است، ساده بوده و به عنوان تمرین به خواننده محول می کنیم.
و اما فرض می کنیم گراف فاقد دور فرد است و می خواهیم اثبات کنیم که دو بخشی است. بدون ایجاد خلل در کلیت مساله، فرض می کنیم که همبند باشد. چرا که اگر ناهمبند باشد، مولفه های همبندی نیز دور فرد ندارند و طبق اثباتی که ارایه خواهیم داد مولفه های همبندی نیز دو بخشی خواهند شد و در نتیجه گراف دو بخشی خواهد بود. فرض کنیم دارای راس باشد از قرار :
چون همبند است، از به تمام راس ها حداقل یک مسیر وجود دارد. اگر طول این مسیر زوج بود. آن را در مجموعه یقرار می دهیم و اگر طول آن فرد بود آن را در مجموعه ی قرار می دهیم. خود را نیز در مجموعه یقرار می دهیم. اولاً ثابت می کنیم چون دور فرد ندارد، زوجیت طول مسیرهایی که از به می روند یکسان است،یعنی اگر از به دو مسیر باشد، یا هر دو با طول فردند یا با طول زوج.
پس از این نتیجه خواهد شد که. در ضمن ثابت خواهیم کرد که هیچ دو راس مجموعه ی به هم متصل نیستند و در ضمن هیچ دو راس مجموعه ی نیز به هم متصل نیستند که حکم مساله خواهد بود.
اگر از به خودش یک مسیر فرد وجود داشته باشد، یعنی یک دور فرد داریم که ممکن نیست. پس از به تنها مسیرهای زوج وجود دارد ( مسیر به طول صفر هم داریم ). اگر از به یکی از راس های دیگر مثلاً یک مسیر با طول زوج و یک مسیر با طول فرد وجود داشته باشد،در آن صورت ثابت می کنیم که یک دور به طول فرد در وجود دارد.
فرد ,
زوج ,
فرض می کنیم . در از شروع کرده و اولین جایی را بیابید که نقاط مشترک دارند. آن را بنامید. از شروع کنید و در تا پیش روید و سپس از مسیر به ترتیب بر عکس از به برگردید. این یک دور است. پس طول زوج دارد. پس در نتیجه از تا در هر در مسیر یا هر دو زوج و یا هر دو فرداند. حال الگوریتم فوق را برای مسیرهای از تا ، که قسمتهایی از هستند، تکرار می کنیم. نهایتاً به دو مسیر از به دست پیدا می کنیم که اشتراک ندارند و طولشان از نظر زوجیت فرق می کند. یعنی اگر طول فرد باشد آنگاه طول زوج خواهد بود و بالعکس.
از چسباندن به هم دوری به طول فرد به وجود می آید که تناقض آشکار است. پس افرازی از راس های گراف اند که اگر دو نقطه از مانند به هم وصل باشند آنگاه دو مسیر وجود دارند.
از به ترتیب به نقاط که هر دو از طول زوج اند. مسیر دوری به طول فرد است که تناقض می باشد. همین طور می توان برای استدلال آورد. پس گراف دو بخشی است.
پس از اثبات قضیه مهم و پرکاربرد بالا به سراغ مطالب ساده تر و بدیهی تر گراف های دو بخشی می‌رویم:
اگر گراف دو بخشی و راسی یک منتظم باشد به ازای چه هایی چنین گرافی وجود دارد؟
حل به سادگی از آنجا که به ازای هر راسی از یک بخش و دقیقاً یک راس از بخش دیگر دقیقاً یک یال داریم، پس تعداد رئوس بخش ها یعنی تعداد یالها
شرط لازم و کافی برای وجود گراف دو بخشی راسی منتظم را بیابید.
.
حل این بار نیز ثابت می کنیم باید برابر باشند.
اثبات فرض کنیم گراف دو بخشیکه یک بخش آن راس و بخش دیگر آن راس دارد، منتظم و از درجه است.
پس تعداد یالهای آن را می توان به دو گونه شمرد:
1.تعداد سرهای منتهی یالها به بخش اول تاست.
2.تعداد سرهای منتهی یالها به بخش دوم تاست.
و هر دو بیانگر تعداد یالها می باشند.
پس داریم: لذا برعکس. باید ثابت کنیم اگر باشد آنگاه گراف منتظم مربوط وجود دارد. که اثبات آن به عنوان تمرین به خواننده محترم واگذار می شود.
از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..
وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران رشد
به دو مجموعه
افراز گردند. به طوری که هنگام رسم گراف
رسم نگردد و هیچ یالی بین راس های مجموعه ی 
نیز ترسیم نشود، گراف
عضو و 
عضو باشد، آنگاه گرافی که هر راس درون
نشان می دهیم.
.
به تمام راس ها حداقل یک مسیر وجود دارد. اگر طول این مسیر زوج بود. آن را در مجموعه ی
قرار می دهیم و اگر طول آن فرد بود آن را در مجموعه ی 
قرار می دهیم. خود 
می روند یکسان است،یعنی اگر از
. در ضمن ثابت خواهیم کرد که هیچ دو راس مجموعه ی 
فرد , 
زوج , 
. در 
از 
شروع کرده و اولین جایی را بیابید که 
نقاط مشترک دارند. آن را
بنامید. از 
تا
از 
به
فرد باشد آنگاه طول 
زوج خواهد بود و بالعکس.
افرازی از راس های گراف اند که اگر دو نقطه از
به هم وصل باشند آنگاه دو مسیر
دوری به طول فرد است که تناقض می باشد. همین طور می توان برای
هایی چنین گرافی وجود دارد؟
منتظم را بیابید.
.
تاست.
تاست.
باشد آنگاه گراف