چند سوال خوب
(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 سوال جدید به همراه حل ها رو مِی زارم.
- ۸۹/۰۱/۲۶