به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
94 بازدید
سوال شده در دانشگاه توسط maara

گرافی با چهار راس را در نظر بگیرید که از لحاظ شکلی مربعی است که یک ضلع آن را حذف کرده ایم.نشان دهید که این گراف کوهن مکالی است.آیا این گراف با گراف دو بخشی ایزومرف است.اگر جواب مثبت است تناقضی با قضیه ی 9.1.14 پیش نمی آید؟ در حالت کلی چگونه میتوان گراف های کوهن مکالی را از روی شکل تشخیص داد.

مرجع: سوال 9.12 کتاب هرزگ هیبی و کتاب villareal

1 پاسخ

+1 امتیاز
پاسخ داده شده توسط erfanm

کوهن مکالی است از آنجایی که کردال است و برای گرافهای کردال کافیه $ unmixed $ باشند که به وضوح چنین است(تنها مجموعه پوشش راسی مینیمال آن مجموعه های $\{1,3\} $و$\{2,4\} $هستند)

enter image description here

اما این گراف را میتوان به صورت زیر نگاه کرد که در این صورت یک گراف دوبخشی است(برای هماهنگی با قضیه $9.1.14$ آن را به صورت زیر نمایش میدهیم)

enter image description here

در حالت کلی نمیتوان از روی ظاهر کوهن مکالی بودن گرافها را تشخیص داد اما قضایایی نظیر $9.3.14$و $9.1.14$ برای حالت های خاص ابزارهایی را به ما میدهند.

مثلا در کردالها کافیه $ unmixed $ باشند یعنی تمام مینیمال پوشش راسی ها دارای یک کاردینالیتی باشند.

دارای دیدگاه توسط maara
ممنون از پاسختون.البته برای تشخیص کوهن مکالی بودن گراف کردال  انگار علاوه بر یکدست  بودن باید بشه  N رو به صورت اجتماع فست های دارای راس آزاد هم نوشت.که این گراف این ویژگی رو هم داره.بابت نوع برچسب بندی با 9.1.14 به تناقض میرسیدم که با پاسخ شما رفع شد.
دارای دیدگاه توسط erfanm
یکدست بودن کافیه

با توجه به اینکه اخیرا هزینه های نگهداری سایت افزایش چشمگیر چند برابری داشته، محفل ریاضی نیازمند حمایت مالی شما است.

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود

ابزارها:

سرگرمی: سودوکو جدید

رسم نمودار: Geogebra جدید

...