This wiki has no edits or logs made within the last 45 days, therefore it is marked as inactive. If you would like to prevent this wiki from being closed, please start showing signs of activity here. If there are no signs of this wiki being used within the next 15 days, this wiki may be closed per the Dormancy Policy. This wiki will then be eligible for adoption by another user. If not adopted and still inactive 135 days from now, this wiki will become eligible for deletion. Please be sure to familiarize yourself with Miraheze's Dormancy Policy. If you are a bureaucrat, you can go to Special:ManageWiki and uncheck "inactive" yourself. If you have any other questions or concerns, please don't hesitate to ask at Stewards' noticeboard.

گراف دو بخشی

از shaazzz
پرش به ناوبری پرش به جستجو

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

رابطه با دور فرد[ویرایش]

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

اثبات[ویرایش]

اگر گراف دارای دور فرد باشد، آن گاه خود آن دور فرد به بیش از دو رنگ برای رنگ شدن نیاز دارد پس گراف دو بخشی نیست.

اگر گراف دارای دور به طول فرد نباشد، آنگاه درخت DFS آن بین طبقات هم زوجیتش، هیچ یالی ندارد ( اگر داشته باشد آن یال و یال های درخت دور به طول فرد تشکیل می دهند. پس می توان طبقات زوج را با یک رنگ و طبقات فرد را با رنگی دیگر رنگ کرد و هیچ یالی دو راس هم رنگ را به هم وصل نمی کند. پس گراف دو بخشی است.

مسائل مرتبط[ویرایش]