گراف دو بخشی

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

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

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

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

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

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

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

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