Parham MLK
کاربر نیمه‌حرفه‌ای
- ارسال‌ها
- 250
- امتیاز
- 675
- نام مرکز سمپاد
- شهید سلطانی
- شهر
- کرج
پاسخ : دایره
. . . چرا هیچکس اثبات نمیکنه؟؟؟
جواب 8 میشه. این هم اثباتش (فقط باید یکم گراف بلد باشید!):
توی گراف ها یه رابطه هست به نام رابطه ی اویلر.
این رابطه میگه اگه توی گراف هیچ دو یالی همدیگر رو قطع نکنن، رابطه ی زیر برقراره:
V: تعداد رأس ها
E: تعداد یال ها
اثباتش رو هم حال ندارم بگم!
طبق این رابطه و فرض سوال (V=7):
از فرمول بالا مشخصه که هر چی F بیشتر باشه، E هم بیشتره!
هر ناحیه توسط دقیقاً یک "دور" احاطه شده!
پس بهتره که طول دور های ما مینیمم باشن تا تعدادشون بیشتر بشه! (مینیمم طول هر دور 3 هست!)
به ازای هر ناحیه، حداقل 3 تا یال داریم که اون ناحیه رو احاطه کردن و هر یال هم توی 2 ناحیه شمرده شده. پس:
حالا:
راه من یه مقدار پیچیده بود . . . فکر کنم راه آسون تری هم باشه!
اگر با راه حل من مشکلی داشتید، بگید تا توضیح بدم! ( آخه خیلی بد توضیح دادم! )
این هم یه مثال با 8 جاده!
[img=http://dc316.4shared.com/img/6VpOyp7T/1271120380.jpg]
. . . چرا هیچکس اثبات نمیکنه؟؟؟
جواب 8 میشه. این هم اثباتش (فقط باید یکم گراف بلد باشید!):
توی گراف ها یه رابطه هست به نام رابطه ی اویلر.
این رابطه میگه اگه توی گراف هیچ دو یالی همدیگر رو قطع نکنن، رابطه ی زیر برقراره:
F+V=E+2
F: تعداد ناحیه هاV: تعداد رأس ها
E: تعداد یال ها
اثباتش رو هم حال ندارم بگم!
طبق این رابطه و فرض سوال (V=7):
F+7=E+2 ==>
F = E - 5
یه رابطه ی دیگه هم باید بین F و E پیدا کنیم:F = E - 5
از فرمول بالا مشخصه که هر چی F بیشتر باشه، E هم بیشتره!
هر ناحیه توسط دقیقاً یک "دور" احاطه شده!
پس بهتره که طول دور های ما مینیمم باشن تا تعدادشون بیشتر بشه! (مینیمم طول هر دور 3 هست!)
به ازای هر ناحیه، حداقل 3 تا یال داریم که اون ناحیه رو احاطه کردن و هر یال هم توی 2 ناحیه شمرده شده. پس:
3F=2E
حالا:
F = E - 5
3F = 2E
==>
E = 15 && F = 10
خوب . . . پس ما حداکثر میتونیم 15 تا یال داشته باشیم. 7 تا یال هم که رسم شده! پس:3F = 2E
==>
E = 15 && F = 10
جواب میشه 8
راه من یه مقدار پیچیده بود . . . فکر کنم راه آسون تری هم باشه!
اگر با راه حل من مشکلی داشتید، بگید تا توضیح بدم! ( آخه خیلی بد توضیح دادم! )
این هم یه مثال با 8 جاده!
[img=http://dc316.4shared.com/img/6VpOyp7T/1271120380.jpg]
