به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
0 امتیاز
355 بازدید
در دانشگاه توسط kani1313 (77 امتیاز)
برچسب گذاری دوباره توسط AmirHosein

چرا $C_4$ یک گراف دو بخشی کامل است؟

توسط AmirHosein (19,718 امتیاز)
ویرایش شده توسط AmirHosein
@kani1313 آیا تعریف گراف دوبخشی کامل را نگاه انداخته‌اید؟ یک دور به درازای ۴ بکشید. بعد نگاه کنید آیا می‌توانید دو مجموعه از گره‌ها معرفی کنید که هر یال دلخواهی که بردارید یک انتهایش در یکی و انتهای دیگرش در دیگری باشد؟ اگر بلی آنگاه گراف دوبخشی دارید. سپس نگاه کنید یال دیگری ممکن است بیفزائید که جزو یال‌های این دور با درازای چهار نباشد ولی هنوز یک گره‌اش در مجموعهٔ یکم و گرهٔ دومش در مجموعهٔ دوم باشد؟ اگر بلی آنگاه گراف دوبخشی‌تان کامل نیز است. چون یک گراف با چهار گره و چهار یال دارید، زمان لازم برای کشیدن و نگاه کردن به آن و چک کردن این دو شرط زیاد نخواهد بود.

1 پاسخ

+1 امتیاز
توسط کیوان عباس زاده (3,110 امتیاز)

قضیه ای است که بیان می کند یک گراف دوبخشی است اگر و تنها اگر فاقد دور فرد (

یعنی دوری که به تعداد فرد راس دارد ) باشد .

اثبات این قضیه در کتاب نظریه گراف باندی و مورتی آمده است .

چون $ C_{4} $ فاقد دور فرد است پس دو بخشی است .

enter image description here

پس می توان رئوس گراف $ C_{4} $ را به دو بخش $X= \lbrace 1,4\rbrace $ و$Y= \lbrace 2,3\rbrace $ افراز کرد و

در بخش $X$ دو راس $1,4$ و در بخش $Y$ دو راس $2,3$ به هم متصل نمی باشند و هریال

گراف یک سرش در $X$ و سر دیگرش در $Y$ است .

بزرگترین ریاضیدانان، همچون ارشمیدس، نیوتن و گاوس، همواره نظریه و کاربردها را در اندازه ی یکسان در هم می آمیزند.
...