روش اجرای آزمونک
برای تعیین عدد رنگی، هم یک رنگآمیزی معتبر بساز و هم دلیل بیاور چرا رنگ کمتر ممکن نیست. روش کامل در راهنمای رنگآمیزی رأس آمده است.
۱۰ تمرین عدد رنگی
سؤال 1
عدد رنگی گرافی بدون یال و با 5 رأس چیست؟
پاسخ تشریحی
هیچ دو رأسی مجاور نیستند؛ یک رنگ برای همه کافی است، پس χ=1.
سؤال 2
عدد رنگی یک مسیر با 6 رأس چیست؟
پاسخ تشریحی
رنگها را یکیدرمیان میدهیم. چون یال وجود دارد حداقل دو رنگ لازم است؛ χ=2.
سؤال 3
عدد رنگی یک دور 4 رأسی را بیاب.
پاسخ تشریحی
دور زوج دو بخشی است و با رنگهای متناوب رنگ میشود؛ χ=2.
سؤال 4
عدد رنگی یک دور 5 رأسی چیست؟
پاسخ تشریحی
دو رنگ در انتهای دور فرد تعارض میسازد و سه رنگ کافی است؛ χ=3.
سؤال 5
عدد رنگی گراف کامل K4 چیست؟
پاسخ تشریحی
هر دو رأس مجاورند، پس هر رأس رنگ جدا میخواهد؛ χ(K4)=4.
سؤال 6
گرافی شامل یک مثلث است. چه حد پایینی برای عدد رنگی داریم؟
پاسخ تشریحی
سه رأس مثلث دو به دو مجاورند؛ بنابراین دستکم 3 رنگ لازم است.
سؤال 7
اگر بتوان گرافی را با 3 رنگ رنگ کرد، آیا حتماً عدد رنگی آن 3 است؟
پاسخ تشریحی
خیر؛ این فقط χ≤3 را نشان میدهد. شاید رنگآمیزی دو یا یکرنگی هم ممکن باشد؛ برای برابری باید حد پایین نیز ثابت شود.
سؤال 8
آیا افزودن یک رأس منزوی عدد رنگی یک گراف دارای یال را تغییر میدهد؟
پاسخ تشریحی
خیر؛ رأس منزوی میتواند یکی از رنگهای موجود را بگیرد، پس عدد رنگی تغییر نمیکند.
سؤال 9
گراف دوبخشیِ دارای دستکم یک یال چه عدد رنگی دارد؟
پاسخ تشریحی
دو بخش را دو رنگ میدهیم و وجود یال مانع یکرنگی است؛ بنابراین χ=2.
سؤال 10
دانشآموز رنگ رأسها را فقط بر اساس تفاوت نامها انتخاب میکند. معیار درست چیست؟
پاسخ تشریحی
فقط رأسهای مجاور باید رنگ متفاوت داشته باشند. رأسهای نامجاور میتوانند همرنگ باشند؛ هدف کمینهکردن تعداد رنگهاست.
چکلیست خودتصحیح
- مجاورت رأسها را درست خواندم.
- یک رنگآمیزی معتبر برای حد بالا ساختم.
- با یال، مثلث، دور فرد یا زیرگراف کامل حد پایین دادم.
- رأسهای نامجاور را بیدلیل جدا نکردم.
- کمینهبودن تعداد رنگها را توضیح دادم.