چند سوال خوب

(1

چند رنگ آمیزی سیاه وسفید از جدول m*n وجود داره که در هر مربع 2*2 دقیقا 2 تا سیاه باشد؟

(2 

همان مساله با این شرط که زوج تا سیاه در هر 2*2 باشد نه لزوما 2 تا.

(3

یه گراف کامل وزن دار داریم که راسهاش مجموعه ای از نقاط روی صفحه اند و وزن هر یال فاصله ی اقلیدسی راس هایش است. اگر مجموع وزن یالهای زیر درخت فراگیر با کمترین مجموع وزن بین همه ی زیر درخت های فراگیر را  T و مجموع وزن یالهای دور هامیلتونی با کمترین مجموع وزن بین همه ی دور های هامیلتونی را C بگیریم. ثابت کنید C حداکثر   2T است.از این که یال ها در حمار صدق میکنن استفاده کنین.   

(4

ثابت کنید یال های گراف کامل n راسی را میتوان طوری جهتدهی کرد که هر راس بتواند با مسیر جهتدار به طول 1 یا 2 به هر راس دیگر برسد اگر وتنها اگر n=4 یا 2  نباشد

(5

اگر E تعداد یالهای یک گرافی که دور زوج ندارد باشد باشد ثابت کنین E  حداکثر

3n-3)/2 ) میباشد.

n تعداد راس هاس!

(6

این سوالو تو نظرات میگم که الگوریتمیم هس.

موفق باشین!

هفته ی بعد 6 سوال جدید به همراه حل ها رو مِی زارم.