پاسخ : گراف
نمیدونم با اونی که گودرز نوشته هم حل می‌شه یا نه، ولی خیلی ساده تر هم می‌شه با قضیه Dirac حلش کرد .اگه استقرا بزنیم روی n خیلی راحت میتونید مساله رو به این حالت تبدیل کنید که درجه هر راسی حداقل
باشه .حالا طبقه Dirac گراف همیلتونی می‌شه . باقیشم سادست دیگه (هر ۲ راسی همسایه مشترک دارن و ....)
Dirac's Theorem -- from Wolfram MathWorld
نمیدونم با اونی که گودرز نوشته هم حل می‌شه یا نه، ولی خیلی ساده تر هم می‌شه با قضیه Dirac حلش کرد .اگه استقرا بزنیم روی n خیلی راحت میتونید مساله رو به این حالت تبدیل کنید که درجه هر راسی حداقل
Dirac's Theorem -- from Wolfram MathWorld
آخرین ویرایش توسط مدیر
پاسخ : گراف
منم راهم مث آقا گودرزه میدونیم حداقل n/2 تا مثلث داریم حالا یه گراف دوبخشی تعریف کنیم یه بخش مثلثا یه بخش راسا حالا هر کدوم از بالاییا که مثلثن درجشون 3 است و پایینیا اگه درجه 2 نداشنه باشن تو شمردن یالها از دوطرف به تناقض میرسیم پس پایینیا حداقل یه راسه درجه 2 دارن و تمام یه نفر 3 ما پیش اینو به عنوان سوال TSTایران به من قالب کرد درسته امیرخان؟
منم راهم مث آقا گودرزه میدونیم حداقل n/2 تا مثلث داریم حالا یه گراف دوبخشی تعریف کنیم یه بخش مثلثا یه بخش راسا حالا هر کدوم از بالاییا که مثلثن درجشون 3 است و پایینیا اگه درجه 2 نداشنه باشن تو شمردن یالها از دوطرف به تناقض میرسیم پس پایینیا حداقل یه راسه درجه 2 دارن و تمام یه نفر 3 ما پیش اینو به عنوان سوال TSTایران به من قالب کرد درسته امیرخان؟