منو
 کاربر Online
1017 کاربر online

گرافهای دوبخشی

چاپ
علوم ریاضی > علو م رایانه



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


گراف دو بخشی

اگر راس های گراف به دو مجموعه افراز گردند. به طوری که هنگام رسم گراف، هیچ یالی بین راس های مجموعه ی رسم نگردد و هیچ یالی بین راس های مجموعه ی نیز ترسیم نشود،‌ گراف را یک گراف دو بخشی نامیم.
اگر دارای عضو و دارای عضو باشد،‌ آنگاه گرافی که هر راس درون را به همه ی راس های وصل کرده باشد را گراف دو بخشی کامل نامیده و با نشان می دهیم.

مثال

img/daneshnameh_up/5/5a/mco0082a.jpg

به راحتی می توان دریافت که تعداد یالهای یک گراف دو بخشی کامل برابر است با
.


قضیه

گراف دو بخشی است اگر و تنها اگر دارای هیچ دوری به طول فرد نباشد.
اثبات
اگر دو بخشی باشد آنگاه اثبات این که هر دور در به طول زوج است، ساده بوده و به عنوان تمرین به خواننده محول می کنیم.
و اما فرض می کنیم گراف فاقد دور فرد است و می خواهیم اثبات کنیم که دو بخشی است. بدون ایجاد خلل در کلیت مساله،‌ فرض می کنیم که همبند باشد. چرا که اگر ناهمبند باشد،‌ مولفه های همبندی نیز دور فرد ندارند و طبق اثباتی که ارایه خواهیم داد مولفه های همبندی نیز دو بخشی خواهند شد و در نتیجه گراف دو بخشی خواهد بود. فرض کنیم دارای راس باشد از قرار :

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


فرد ,

زوج ,

فرض می کنیم . در از شروع کرده و اولین جایی را بیابید که نقاط مشترک دارند. آن را بنامید. از شروع کنید و در تا پیش روید و سپس از مسیر به ترتیب بر عکس از به برگردید. این یک دور است. پس طول زوج دارد. پس در نتیجه از تا در هر در مسیر یا هر دو زوج و یا هر دو فرداند. حال الگوریتم فوق را برای مسیرهای از تا ، که قسمتهایی از هستند،‌ تکرار می کنیم. نهایتاً به دو مسیر از به دست پیدا می کنیم که اشتراک ندارند و طولشان از نظر زوجیت فرق می کند. یعنی اگر طول فرد باشد آنگاه طول زوج خواهد بود و بالعکس.
از چسباندن به هم دوری به طول فرد به وجود می آید که تناقض آشکار است. پس افرازی از راس های گراف اند که اگر دو نقطه از مانند به هم وصل باشند آنگاه دو مسیر وجود دارند.
از به ترتیب به نقاط که هر دو از طول زوج اند. مسیر img/daneshnameh_up/2/20/mco0082b.jpg دوری به طول فرد است که تناقض می باشد. همین طور می توان برای استدلال آورد. پس گراف دو بخشی است.
پس از اثبات قضیه مهم و پرکاربرد بالا به سراغ مطالب ساده تر و بدیهی تر گراف های دو بخشی می‌رویم:

مثال

اگر گراف دو بخشی و راسی یک منتظم باشد به ازای چه هایی چنین گرافی وجود دارد؟
حل
به سادگی از آنجا که به ازای هر راسی از یک بخش و دقیقاً‌ یک راس از بخش دیگر دقیقاً‌ یک یال داریم،‌ پس تعداد رئوس بخش ها یعنی تعداد یالها

مثال

شرط لازم و کافی برای وجود گراف دو بخشی راسی منتظم را بیابید.
.
حل
این بار نیز ثابت می کنیم باید برابر باشند.
اثبات
فرض کنیم گراف دو بخشیکه یک بخش آن راس و بخش دیگر آن راس دارد،‌ منتظم و از درجه است.
پس تعداد یالهای آن را می توان به دو گونه شمرد:
1.تعداد سرهای منتهی یالها به بخش اول تاست.
2.تعداد سرهای منتهی یالها به بخش دوم تاست.
و هر دو بیانگر تعداد یالها می باشند.
پس داریم:
لذا
برعکس. باید ثابت کنیم اگر باشد آنگاه گراف منتظم مربوط وجود دارد. که اثبات آن به عنوان تمرین به خواننده محترم واگذار می شود.

پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0076.pdf

همچنین ببینید




تعداد بازدید ها: 18422


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..