به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
87 بازدید
سوال شده در دانشگاه توسط 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
یکدست بودن کافیه
لطفا ما را در شبکه های اجتماعی دنبال کنید:
به محفل ریاضی ایرانیان خوش آمدید!
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
تلگرام محفل ریاضی
64 نفر آنلاین
1 عضو و 63 مهمان در سایت حاضرند
بازدید امروز: 4546
بازدید دیروز: 4732
بازدید کل: 4867909
...