فرض کنید n فرد داریم که هر یک از انها دارای تعدادی دوست است از نفر اول شروع میکنیم هر شب یک نفر میهمانی میدهد و تمام دوستانش را دعوت میکند و در میهمانی تمام دوستانش دوبه دو باهم دوست میشوند اگر هر یک یکبار میهمانی دهند و دراخر کار دو نفر داشته باشیم که هنوز با هم دوست نشده اند ثابت کنید هرچند بار دیگر که میهمانی گرفته شود انان هیچگاه باهم دوست نمیشوند .
پاسخ : مسائل جالب گراف
تنها در صورتی دو نفر طی مهمانی با هم دوست میشوند که در گراف مورد نظر راس های آنها به یکدیگر مسیر داشته باشند
دوتا چیز باید ثابت بشن:
1- اگه دو تا راس به هم مسیر داشته باشن طی یک دور کامل مهمانی به هم وصل میشوند
2- اگه دو راس به هم مسیر نداشته باشند هرگز تعداد هر تعدادی مهمانی به هم وصل نمیشوند
فرض کنیم A به B مسیر دارد
کوتاه ترین مسیر بین آنها رو در نظر میگیریم
اگر طول مسیر 1 باشد که به هم وصل هستند
اگر بیشتر از یک باشد (فرض میکنیم n) طی هر مهمانی که یکی از راس های مسیر برگزار میکند طول مسیر یکی کم میشود
تعداد راس های بین مسیر n-1 است و بنابراین پس از برگزاری تمام مهمانی ها طول آن 1 میشود و راس ها به هم وصل میشوند
برای دومی چیزی به ذهنم نمیرسه خودتون فکر کنید
جواب بدست اوردین اینجا بزارین
تنها در صورتی دو نفر طی مهمانی با هم دوست میشوند که در گراف مورد نظر راس های آنها به یکدیگر مسیر داشته باشند
دوتا چیز باید ثابت بشن:
1- اگه دو تا راس به هم مسیر داشته باشن طی یک دور کامل مهمانی به هم وصل میشوند
2- اگه دو راس به هم مسیر نداشته باشند هرگز تعداد هر تعدادی مهمانی به هم وصل نمیشوند
فرض کنیم A به B مسیر دارد
کوتاه ترین مسیر بین آنها رو در نظر میگیریم
اگر طول مسیر 1 باشد که به هم وصل هستند
اگر بیشتر از یک باشد (فرض میکنیم n) طی هر مهمانی که یکی از راس های مسیر برگزار میکند طول مسیر یکی کم میشود
تعداد راس های بین مسیر n-1 است و بنابراین پس از برگزاری تمام مهمانی ها طول آن 1 میشود و راس ها به هم وصل میشوند
برای دومی چیزی به ذهنم نمیرسه خودتون فکر کنید
جواب بدست اوردین اینجا بزارین
پاسخ : مسائل جالب گراف
حلت درسته اما دومی که بدیهیه اگر بینشون هیچ مسیری وجود نداشته باشه گراف ناهمبنده و اونا دو تا راس توی خوشه های متفاوتی هستند که با توجه به مسئله اگر گراف ناهمبند باشه در اخر باز ناهمبند میمونه یه جورایی بدیهیه .
سوال 2.امتحانی n سوال داره هر سوال توسط 3 نفر حل شده و برای هر دو سوال تنها یه نفر وجود داره که 2 سوال رو حل کرده و هیچ کسی تمام سوالات رو حل نکرده ماکزیمم n چنده ؟
حلت درسته اما دومی که بدیهیه اگر بینشون هیچ مسیری وجود نداشته باشه گراف ناهمبنده و اونا دو تا راس توی خوشه های متفاوتی هستند که با توجه به مسئله اگر گراف ناهمبند باشه در اخر باز ناهمبند میمونه یه جورایی بدیهیه .
سوال 2.امتحانی n سوال داره هر سوال توسط 3 نفر حل شده و برای هر دو سوال تنها یه نفر وجود داره که 2 سوال رو حل کرده و هیچ کسی تمام سوالات رو حل نکرده ماکزیمم n چنده ؟
آخرین ویرایش توسط مدیر