ماراتن ترکیبیات
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:7dd799f9ad]
[/center:7dd799f9ad]سوال بیست و سوم:
در ایالت ((دولفینا)) ، n شهر وجود دارد و هر دو شهر با یک جاده به هم مربوط هستند. جاده ها یک طرفه اند.ثابت کنید برای
و
می توان جهت حرکت در جاده ها را طوری انتخاب کرد که بتوان از هر شهر به هر شهر دیگر رفت بی آن که بیش از یک شهر دیگر در سر راه باشد. همچنین ثابت کنید برای
و
نمی توان چنین سازمانی داد.
منبع: مهم ترین مساله ها و قضیه های ریاضی ، شکلیارسکی-چنتسوف-یاگلوم،ترجمه پرویز شهریاری - ابراهیم عادل
در ایالت ((دولفینا)) ، n شهر وجود دارد و هر دو شهر با یک جاده به هم مربوط هستند. جاده ها یک طرفه اند.ثابت کنید برای
منبع: مهم ترین مساله ها و قضیه های ریاضی ، شکلیارسکی-چنتسوف-یاگلوم،ترجمه پرویز شهریاری - ابراهیم عادل
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
shoki گفت
این سوال (23) 22.7.11 صفحه ی 315 علی پور هست ... البته در الفبا هم اومده...
در مورد سوال 22 هم اگر دقت می کردید من گفتم راه حلش اومده نه حلش ...
در مورد سوال 22 هم اگر دقت می کردید من گفتم راه حلش اومده نه حلش ...
ضمنا متاسفانه من نمی تونم همه سوالات علی پور رو چک کنم تا ببینم یک سوال هست یا نیست.
من از کتاب دیگه ای نوشتم. با این حال یک سوال دیگه گذاشتم که امیدوارم آقای علی پور ندیده باشنش.!!
[center:a3502cbde5]ftopicp-19645.html#19645[/center:a3502cbde5]
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:ea2e00043e]23[/center:ea2e00043e]
حالا که این سوال هم تو علی پور هست حلشو می نویسم.
فرض کنید برای n تا شهر بشه ، ثابت می کنیم برای n+2 تا هم میشه. ایتدا برای n شهر این کار را می کنیم. بعد از هر شهر به طرف شهر n+1 ام راه را یک طرفه می کنیم. از شهر n+1 به شهر n+2 راه را یک طرفه می کنیم و از شهر n+2 به همه ی n شهر یک طرفه می کنیم. بدیهی است که شرط برقرار است.
کافی است برای n=3 و n=6 برقراری حکم را بررسی کنیم(به عهده ی خودتان)
حالا که این سوال هم تو علی پور هست حلشو می نویسم.
فرض کنید برای n تا شهر بشه ، ثابت می کنیم برای n+2 تا هم میشه. ایتدا برای n شهر این کار را می کنیم. بعد از هر شهر به طرف شهر n+1 ام راه را یک طرفه می کنیم. از شهر n+1 به شهر n+2 راه را یک طرفه می کنیم و از شهر n+2 به همه ی n شهر یک طرفه می کنیم. بدیهی است که شرط برقرار است.
کافی است برای n=3 و n=6 برقراری حکم را بررسی کنیم(به عهده ی خودتان)
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
سوال بیست و چهارم
[center:f8e327b966]
[/center:f8e327b966]سوال بیست و چهارم:
در شهر ((لیستر)) می توان از طریق مترو از هر ایستگاه به هر ایستگاه دیگری رفت.اگر لازم باشد می توان قطار را عوض کرد. ثابت کنید ایستگاهی وجود دارد که اگر بسته شود باز هم می توان از هر ایستگاهی به هر ایستگاه دیگر رفت. وقتی ایستگاهی بسته شود ، نمی توان از آن عبور کرد. (ساده تر از این سوال پیدا نمی شه!!)
[center:f8e327b966]
در شهر ((لیستر)) می توان از طریق مترو از هر ایستگاه به هر ایستگاه دیگری رفت.اگر لازم باشد می توان قطار را عوض کرد. ثابت کنید ایستگاهی وجود دارد که اگر بسته شود باز هم می توان از هر ایستگاهی به هر ایستگاه دیگر رفت. وقتی ایستگاهی بسته شود ، نمی توان از آن عبور کرد. (ساده تر از این سوال پیدا نمی شه!!)
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:b9b3406311]
[/center:b9b3406311]چون خودم هم همزمان به سوالات فکر می کنم ، خودم جوابشو می ذارم:
یک گراف از این شبکه تشکیل می دهیم. اگر گراف درخت باشد (دور نداشته باشد) می توانیم یکی از راسهای انتهایی را حذف کنیم.
اما اگر دور داشته باشد ، می توانیم هر یک از راس های داخل دور را حذف کنیم.
به همین سادگی ، به همین خوشمزگی ، ...
یک گراف از این شبکه تشکیل می دهیم. اگر گراف درخت باشد (دور نداشته باشد) می توانیم یکی از راسهای انتهایی را حذف کنیم.
اما اگر دور داشته باشد ، می توانیم هر یک از راس های داخل دور را حذف کنیم.
به همین سادگی ، به همین خوشمزگی ، ...
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
سوال بیست و پنجم
ftopicp-19661.html#19661
ضمنا ببخشید که مسئله را به صورت عکس گذاشتم.
http://up.iranblog.com/37261/1267303835.jpg
ftopicp-19661.html#19661
ضمنا ببخشید که مسئله را به صورت عکس گذاشتم.