سوال های دوره تابستان

مساله اول: مهره ها......................................................................................................... 30 نمره

دو مساله زیر را در نظر بگیرید:

مسالهA: گرافGو تعدادی مهره روی بعضی رأس های آن داده شده است. می خواهیم مهره ها را روی یال ها طوری حرکت دهیم که زیر گراف القایی رأس های که شامل حداقل یک مهره اند همبند شده و مجموع حرکات مهره ها نیز کمینه شود.

مسألهB :
گراف2بخشىHکهمجموعه ی دو بخش آنXوYمى باشند دادهشده است. میخواهیم کوچیکترین زیر مجموعۀXمانندSرا پیدا کنیم بهطورى کهN(S)=Y
ثابت کنید اگر براى مسألهA الگوریتمچندجمله ایوجود داشته باشد براى مسألهBنیزالگوریتمچندجمله ایوجود دارد.

مساله دوم: رنگ کردن مربع ها........................................................................................... 35 نمره

nمربح به ضلح واحد طوری در صفحه قرار گرفته اند که اضلاع شان موازی محور های مختصات بوده و مختصات طولی یا عرضی هیچ دو مربعی برابر نیست. یک عددkبه شما داده شده است و به شما گفته شده که هیچk+1مربعی وجود ندارد که هر دوتایشان با هم اشتراک داشته باشند.

ثابت کنید می توان این مربح ها را با حداکثر2k-1رنگ,طوری رنگ کرد که رنگ هرمربعی که با هم اشتراک دارند متفاوت باشد.

مساله سوم: مجموعه........................................................................................................15 نمره

ثابت کنید تعداد زیرمجموعه های مجموعه ی{1,2,…n}که دارای میانگین طبیعی هستند زوج تا هستند.

مساله چهار : شمارش........................................................................................................ 10 نمره

تعداد گراف های همبند بیشتر است یا نا همبند ؟

مساله پنجم : باز هم مساله!؟؟؟ ............................................................................................... 0 نمره

سوال های 1و2و5 امتحان دوره تابستان 85 هستش !!! سوال 3 حل مساله دوره ی ما(86)سوال 4 هم تمرین گراف سال 85 !!!

اگر مرحله 2 قبول شید 100% یک امتحان با این شکل خواهید دید !

مساله ها این جوری شماره دارند و نمرشون هم جلوش نوشته شده !