شاززز

شاززز

اینجا وبسایت آزاد المپیاد کامپیوتره! ;)
واسه ی همه ی سطوح از تازه کارها تا طلای جهانی!

بایگانی

چند سوال خوب

پنجشنبه, ۲۶ فروردين ۱۳۸۹، ۰۵:۱۴ ب.ظ
چند سوال خوب داشتم گفتم برا قبل مرحله2 خوب باشه حل کنین.

(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 سوال جدید به همراه حل ها رو مِی زارم.

  • ۸۹/۰۱/۲۶
  • شااززز منگولیا

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی