علی راعی عزیز ! بگو دقیقا کجای سوال رو نفهمیدی تا بیشتر توضیح بدم ، کلیت سوال اینه که هر 11 تا شهری رو که در نظر بگیریم ، حداقل 2 تا شهر باشن که بینشون جاده است ، سوال در واقع تعداد جاده ها رو میخواد ! همین .
2015-07-26 13:11:33 -0500 نارنجیآمار پرسش:
- پرسیده شده: 2015-07-26 06:18:09 -0500
- مشاهده شده: 251 بار
- بروز شده: 2015-07-27 01:33:54 -0500
پرسش‌های مشابه:
پیدا کردن گراف دوبخشی کامل یکرنگ
حداکثر تعداد یال‌های گراف بدون مثلث
اثبات همبند بودن مکمل گراف ناهمبند
همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1
رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ
پیدا کردن مولفه های قویا همبند گراف جهت دار
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
جاده کشی مطلوب در کشور کاهولند !!
رییس جمهور کشور کاهولند به بچه های المپیاد کامپیوتری کشورش یک ماموریت داده ! کشور کاهو 100 تا شهر داره ، رییس جمهور کشور از بچه ها یک جاده کشی مطلوب می خواد . جاده کشی ای مطلوب تعریف میشه که هر یازده شهری از این کشور رو در نظر بگیریم ، حداقل 2 شهر وجود داشته باشه که بینشان جاده داشته باشیم. از اونجایی که کشور کاهو در رکود اقتصادی به سر میبره ، مسئولین کشور می خوان که کمترین تعداد جاده رو بسازن تا جاده کشی مطلوب داشته باشن.
الف ) حداقل تعداد جاده برای جاده کشی مطلوب در کاهولند رو بدست بیارید .
ب ) مثالی برای قسمت الف ارائه دهید .
2015-07-26 06:18:09 -0500
نارنجی 485 ● 5 ● 11 ● 20
نظرات
1 پاسخ
سلام !
یکم فک کردم روی این سوال دیدم سوال جالبیه معکوس قضیه تورانه :د (قضیه توران که میدونید چیه؟)
تعریف کوچکی از قضیه کلیدی توران : توران میخواد بگه بیشترین تعداد یال برای این که ما $k_{r}$ نداشته باشیم چقدره همین !
توی گراف $G$ رو مکمل همین گراف خودمون (کاهولند) بگیر .$G$ هرچه بیشتر یال داشته باشه بیشتر به نفع ماست (:د) و یه خصوصیت دیگه هم داره اینکه زیر گراف $k_{11}$ نداره (چون اگه داشته باشه توی کاهولند حتما 11 تا هستند که یالی بین آنها نیست) ما نیز از این خصوصیت استفاده میکنیم و توران میزنیم رو $G$ . پس طبق توران $Max(E(G))=\frac{n}{2}.\frac{r-2}{r-1} \xrightarrow[r=11]{n=100} Max(E(G))=4500$ (اثبات بهینگی ش هم برید از توران بپرسید !) پس گراف اصلی مون $\binom{100}{2}-4500=450$ یال داره .
الف :جواب :450
ب: مثال : مثالش هم مکمل قبلیه است دیگه بیاید راس های کاهولند رو به دسته های 10 تایی تقسیم کنید بعد توی هر 10 تایی 45 تا یال میزاریم (اون 10 تا راس رو گراف کامل 10 راسی میکنیم ) بکه در مجموع 450 یال به کار رفته و در شرایط صدق میکنه (هر 11 راس رو که بگیریم 2 تاش داخل یک دسته میافتن پس به هم یال دارند .)
2015-07-27 01:30:36 -0500
چشمک 2291 ● 29 ● 67 ● 119
نظرات
آفرین چشمک عزیز ! فقط خوب بود مستقیما حکم رو ثابت می کردی و به قضیه ای ارجاع نمی دادی .
2015-07-27 09:30:37 -0500 نارنجی