مسابقه‌ی تصادفی

 
 
 نقاط رنگی
نقاط رنگیمسابقه كامپيوتر
مسابقه شماره‌ی ۱۷۹

تعدادی نقطه و پاره‌خط مانند شکل زیر موجود است.رنگ‌آمیزی نقاط را بدین ترتیب تعریف می‌کنیم؛به هر نقطه یک رنگنسبت می‌دهیم،به طوری که دو نقطه که با یک پاره‌خط به هم وصل شده‌اند ،هم‌رنگ نباشند.گزینه‌ی صحیح را انتخاب کنید.

الف) می‌توان نقاط را با 3 رنگ،ر رنگ‌آمیزی کرد

ب) می‌توان نقاط را با 4 رنگ، رنگ‌آمیزی کرد

ج) با حذف هر پاره خط، نقاط را می‌توان با 3 رنگ، رنگ‌آمیزی کرد

د) الف و ب و ج

ه‌) ب و ج

 


 

پاسخ : سه راس a , d و e سه رنگ متمایز دارند و نیز سه راس g , d و e نیز سه رنگ متمایز دارند , بنابراین اگر بخواهیم رئوس  را فقط با سه رنگ , رنگ آمیزی کنیم آنگاه a و g هم رنگ خواهند بود. به همین ترتیب معلوم میشود که a و f هم رنگ هستند که در این صورت دو راس f و g که به هم وصل هستند هم رنگ شده و با فرض داده شده تناقض ایجاد میکند.

شکل داده شده را با 4 نوع رنگ به شکل زیر میتوان رنگ کرد :

آبی  : e و b

سبز : g و a

ززرد : f

قرمز :c و d

و همچنین قابل بررسی است که با حذف هر یال رنک آمیزی شکل با سه رنگ امکان پذیر است.

 

1390/12/15 لينک مستقيم

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تایید انصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
خطایی روی داده است.
خطا: بازديدها فعلا" غیر قابل دسترسی می باشد.