به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+2 امتیاز
53 بازدید
در دانشگاه توسط Math_green (107 امتیاز)
ویرایش شده توسط AmirHosein

ثابت کنید که گراف $G$ ناهمیلتونی است هرگاه $G$ گرافی دو بخشی باشد به طوری که دو بخش آن با هم، هم اندازه نباشند. یعنی $ \mid x \mid \neq \mid y \mid $.

تلاش خودم: اگر تعداد راس‌های گراف فرد باشد گراف دور فرد دارد که با دوبخشی بودن آن در تناقض است.

توسط Math_green (107 امتیاز)
تلاش خودم:
اگر تعداد راس های گراف فرد باشد گراف دور فرد دارد که با دو بخشی بودن آن در تناقض است.
توسط AmirHosein (11,165 امتیاز)
@Math_green تلاش خودتان را در ادامهٔ همان متن پرسش بنویسید مانند ویرایشی که برایتان کردم.

1 پاسخ

0 امتیاز
توسط AmirHosein (11,165 امتیاز)
ویرایش شده توسط AmirHosein

احتمالا متن پرسش‌تان را اشتباه نوشته‌اید. اگر فرض کنیم که منظرو متن‌تان است که «یک گراف ناهمیلتونی است اگر و تنها اگر گرافی دوبخشی با تعداد نابرابری گره در دو بخشش باشد» که اصلا همیلتونی بودن و نبودن الزامی به دوبخشی بودن ندارد.

  1. دوبخشی که همیلتونی باشد:

توضیحات تصویر

  1. دوبخشی که همیلتونی نباشد:

توضیحات تصویر

  1. نادوبخشی که همیلتونی باشد:

توضیحات تصویر

  1. نادوبخشی که همیلتونی نباشد:

توضیحات تصویر

پس اصلا گزاره‌ای اگر و تنها اگر برای همیلتونی (یا ناهمیلتونی) با شرط دوبخشی نمی‌توانید بسازید (چه تعداد گره‌ها در دو بخش یکی باشد چه نباشد).

اکنون اگر منظورتان فقط گزارهٔ یک‌طرفه و آن هم در سمت برعکس چیزی که نوشتید باشد، یعنی «یک گراف دوبخشی با تعداد نابرابر گره در دو بخشش حتما ناهمیلتونی است» که در این صورت نمونهٔ شمارهٔ ۱ در بالا برایتان مثال نقض است. برایتان هم باید (از قسمت نخست پاسخ) روشن باشد که چرا اصلا به سراغ سمت دیگر گزاره به شکل یک طرفه نرفتم.


حمایت مالی

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