مسابقه شماره‌ی ۱۷۹
تعدادی نقطه و پاره‌خط مانند شکل زیر موجود است.رنگ‌آمیزی نقاط را بدین ترتیب تعریف می‌کنیم؛به هر نقطه یک رنگنسبت می‌دهیم،به طوری که دو نقطه که با یک پاره‌خط به هم وصل شده‌اند ،هم‌رنگ نباشند.گزینه‌ی صحیح را انتخاب کنید.
الف) میتوان نقاط را با 3 رنگ،ر رنگ‌آمیزی کرد
ب) میتوان نقاط را با 4 رنگ، رنگ‌آمیزی کرد
ج) با حذف هر پاره خط، نقاط را میتوان با 3 رنگ، رنگ‌آمیزی کرد
د) الف و ب و ج
ه) ب و ج
پاسخ : سه راس a , d و e سه رنگ متمایز دارند و نیز سه راس g , d و e نیز سه رنگ متمایز دارند , بنابراین اگر بخواهیم رئوس را فقط با سه رنگ , رنگ آمیزی کنیم آنگاه a و g هم رنگ خواهند بود. به همین ترتیب معلوم میشود که a و f هم رنگ هستند که در این صورت دو راس f و g که به هم وصل هستند هم رنگ شده و با فرض داده شده تناقض ایجاد میکند.
|
شکل داده شده را با 4 نوع رنگ به شکل زیر میتوان رنگ کرد :
آبی : e و b
سبز : g و a
ززرد : f
قرمز :c و d
و همچنین قابل بررسی است که با حذف هر یال رنک آمیزی شکل با سه رنگ امکان پذیر است.
|
 |