از کتاب نظریه گراف باندی و مورتی:
A mouse eats his way through a 3x3x3 cube of cheese by tunneling through all of the 27 1x1x1 subcubes. If he starts at one corner and always moves on to an uneaten subcube, can he finish at the center of the cube?e
سلام. من زبانم ضعیفه. چیزی که از این سوال میفهمم اینه که آیا یک موش میتونه از خونه گوشه ای یک مکعب ۳×۳×۳ یه جوری از همه خونه ها رد بشه که آخرین خونه، خونه مرکزی باشه. یعنی وجود مسیر همیلتونی از گوشه به مرکز. اگه سوال همین باشه جواب من منفیه. فرض کنید خونه های مکعبمونو تعریف کنیم [tex][i,j,k] ; i,j,k\in \{1,2,3\}[/tex]. مختصات خونه مرکزی [tex][2,2,2][/tex] و خونه های کناری میشن: [tex][1,1,1][/tex] ، [tex][1,1,3][/tex] ، [tex][1,3,1][/tex] ، [tex][1,3,3][/tex] ، [tex][3,1,1][/tex] ، [tex][3,1,3][/tex] ، [tex][3,3,1][/tex] و [tex][3,3,3][/tex]. اگه توجه کنید هر حرکتمون باید بگونه ای باشه که یکی 3 مقدار به اندازه یک واحد در بازه مشخص تغییر کنه. به خونه های مرزی توجه کنید که جمع مقادیر مختصاتشون برابر یکی از مقادیر مجموعه [tex]\{3,5,7,9\}[/tex] هست. یعنی جمع مقادیرشون فرده. جمع مقادیر خونه مرکزی هم 6 میشه که زوجه. دنبال مسیر همیلتونی هستیم از 27 نود. پس طول مسیر 26 میشه و با هر حرکت هم به مجموع مقادیر مختصات نقاط یا یک واحد کم میشه و یا یک واحد اضافه میشه. پس بعد از 26 حرکت مسلماً نقطه پایانی دارای جمع مختصات فرد میشه. پس امکان نداره این مسیر همیلتونی به یکی از رئوس با جمع مختصات رئوس زوج از جمله راس مرکزی ختم بشه.
اره / جوابش منفیه / چنین مسیری وجود نداره / استادم هم تقریبا به همین روش حل کرده بود / تو یه کتاب هم دیدم با همین استدلال گفته بود/ ولی من اثبات به یه طریق دیگه یعنی فرمالتر میخوام / به نظرت میتونم چیزی پیدا کنم
نمیدونم. یه شرط لازم برای این مسئه این بود. چون این شرط رو نداشت پس جواب مسئله غلط میشه. فکر کنم منظور طراح سوال همین باشه که برای پیدا کردن مسیر همیلتونی توی یه گراف دو بخشی که یه بخشش k راس و بخش دیگش k-1 راس وجود داره؛ این مسیر فقط میتونه از یکی از رئوس بخش k راسی به یه راس دیگه از همین مجموعه باشه. توی این مسال هم بخش بزرگتر همون بخشیه که شامل رئوس کناری میشه.
این قضیه چیو میگه؟ (میشه صورت قضیه رو کامل بنویسی و مرجع ات هم بگی)/ میگه اگه این شرط نباشه گراف مسیر همیلتونی نداره؟ (ولی این گراف مسیر همیلتونی داره / از راسهای کناری به راس مرکزی نداره)
من که نگفتم مسیر همیلتونی نداره. گفتم گرافش دوبخشیه که یه بخشش k راس و بخش دیگش k-1 راس داره. مسلماً دور همیلتونی نداره (گراف دوبخشی وقتی دور همیلتونی میتونه داشته باشه که تعداد رئوس هر بخش برابر باشن. (نمیدونم منبع داره یا نداره ولی قابل اثباته.)) ولی درصورت داشتن مسیر همیتونی، این مسیر باید از یکی از رئوس بخش بزرگتر شروع بشه و به یکی دیگه از رئوس این بخش ختم بشه. (گراف دوبخشی وقتی میتونه مسیر همیلتونی داشته باشه که اختلاف تعداد اعضای هر بخش ۰ یا ۱ باشه. اگه اختلاف صفر باشه مسلماً مسیر از یک بخش شروع و به بخش دیگه ختم میشه و اگه اختلاف ۱ باشه از بخش بزرگتر هم شروع و هم ختم میشه. (نمیدونم اینم منبع داره یا نداره ولی قابل اثباته.)) توی این گراف هم بخش بزرگتر بخشیه که راس هاش دارای مجموع مختصات فرد هستن. یعنی رئوس کناری و رئوس مرکزی ۶ وجه. تمام مسیرهای همیلتونی باید از یکی از این مجموعه رئوس به یک عضو دیگه از این مجموعه باشن.
(17 مرداد 1391 03:50 ب.ظ)Jooybari نوشته شده توسط: [ -> ]درصورت داشتن مسیر همیتونی، این مسیر باید از یکی از رئوس بخش بزرگتر شروع بشه و به یکی دیگه از رئوس این بخش ختم بشه. (گراف دوبخشی وقتی میتونه مسیر همیلتونی داشته باشه که اختلاف تعداد اعضای هر بخش ۰ یا ۱ باشه. اگه اختلاف صفر باشه مسلماً مسیر از یک بخش شروع و به بخش دیگه ختم میشه و اگه اختلاف ۱ باشه از بخش بزرگتر هم شروع و هم ختم میشه. (نمیدونم اینم منبع داره یا نداره ولی قابل اثباته.)) توی این گراف هم بخش بزرگتر بخشیه که راس هاش دارای مجموع مختصات فرد هستن. یعنی رئوس کناری و رئوس مرکزی ۶ وجه. تمام مسیرهای همیلتونی باید از یکی از این مجموعه رئوس به یک عضو دیگه از این مجموعه باشن.
بله /
قضیه اول که ربطی به این سوال نداره (نمی دونم چرا گفتی) / قضیه دومو چطوری اثبات می کنی (مخصوصاً اونجا که خط کشیدم)؟
مسیر همیلتونی مسیریه که از هر راس دقیقاً یکبار بگذزه. با درنظز گرفتن شرط فرد بودن تعداد رئوس (اختلاف دومجموعه 1 هست پس مجموع اعضاشون فرد میشه.) باید طول مسیر همیلتونی زوج باشه. توی گراف دوبخشی هیچ یالی پیدا نمیشه که از یک راس یک یخش به یه راس دیگه از همون بخش باشه. یعنی مسیرهای بطول 1 از بخش A به بخش B ختم میشه. مسیرهای بطول 2 هم از A به A ختم میشه (یکی از رئوس بخش B نقش واسط رو داره). با استقرا میشه ثابت کرد تمام مسیرهای بطول زوج باید از A به A ختم بشن. مسیری رو درنظر بگیرید که تمام رئوس مجموعه مبدا رو شامل بشه یعنی [tex]a_1.b_1.a_2.b_2....a_{n-1}.b_{n-1}.a_n[/tex] مسیری باشه که از تمام رئوس بخش A بگذره. اگه قرار باشه این مسیر همیلتونی باشه باید از تمام رئوس مجموعه B گذشته باشه. پس مجموعه A باید یک عضو بیشتر از مجموعه B داشته باشه. اگه قرار باشه دو عضو یک مجموعه در این مسیر پشت سر هم بیان شرط دوبخشی بودن گراف نقض میشه. اگه قرار باشه اعضای B بعد از آخرین عضو بیان یکی از شرط های طول زوج مسیر یا دوبخشی بودن گراف نقض میشه. پس مسیر همیلتونی فقط به همین شکل میتونه باشه.
مرسی / لطف کردید/ فکر کنم اینطور اثبات بهتر باشه تا قبلی، نه؟