Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۳:گراف:سوال ۲

سوال ۲

2n+1 راس دور یک دایره در نظر می‌گیریم. هر راس را به تمام راس‌ها جز دو راس مجاورش با یک یال وصل می‌کنیم. می‌خواهیم تمام راس‌ها و تمام یال‌ها را رنگ کنیم، به طوری که:

  1. دو راس متصل به هم، رنگ‌های متفاوت بگیرند.
  2. یک راس و یک یال متصل به هم رنگ‌های متفاوت بگیرند.
  3. دو یال که در یک راس مشترکند، رنگ‌های متفاوت بگیرند.

بدیهی است حداقل 2n1 رنگ مختلف برای این کار لازم است. نشان دهید به ازای n>1 این مقدار رنگ کافی نیست.(باز هم تکرار می‌کنیم که کمان‌های دایره یال مجاورت نیستند.)


ابزار صفحه