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

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

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

الف) می‌توان نقاط را با 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لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  4340
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  4340