یک سوال
- شروع کننده موضوع sayyed
- تاریخ شروع
احسان
کاربر فوق‌فعال
- ارسال‌ها
- 137
- امتیاز
- 19
- نام مرکز سمپاد
- شهید اژهای
- شهر
- اصفهان
- مدال المپیاد
- نقرهی المپیاد کامپیوتر
- دانشگاه
- شریف
- رشته دانشگاه
- مهندسی کامپیوتر
پاسخ : یک سوال
توی یه گراف ساده ی n راسی (n برزگتر از 1)، درجه ی هر راس باید برزگتر یا مساوی 0 باشه و کوچیکتر یا مساوی n-1 ! حالا اگه درجه ی هیچ دو راسی برابر نباشه، یعنی هم باید یه راس با درجه ی 0 توی گراف وجود داشته باشه و هم یه راس با درجه ی n-1 که این هم ممکن نیست! (وقتی درجه ی یه راس 0 باشه یعنی اون راس به هیچ راس دیگه ای یال نداره! پس درجه ی هیچ راس دیگه ای نمی تونه n-1 باشه!!)
این یه سوال معروف درباره ی اصل لانه ی کبوتریه!
به نقل از sayyed :
توی یه گراف ساده ی n راسی (n برزگتر از 1)، درجه ی هر راس باید برزگتر یا مساوی 0 باشه و کوچیکتر یا مساوی n-1 ! حالا اگه درجه ی هیچ دو راسی برابر نباشه، یعنی هم باید یه راس با درجه ی 0 توی گراف وجود داشته باشه و هم یه راس با درجه ی n-1 که این هم ممکن نیست! (وقتی درجه ی یه راس 0 باشه یعنی اون راس به هیچ راس دیگه ای یال نداره! پس درجه ی هیچ راس دیگه ای نمی تونه n-1 باشه!!)
این یه سوال معروف درباره ی اصل لانه ی کبوتریه!
