المپدیا

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

ابزار کاربر

ابزار سایت


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

گراف خوش‌رنگ‌‌پذیر

دنباله‌ی $a_1 … a_n$ از اعداد متفاوت را روی گراف $G$ با $n$ راس و $e$ یال می‌گوییم خوب است، در صورتی که اگر به هر یال $uv$ از $G$ باقی‌مانده‌ی $a_u+a_v$ بر $e$ را نسبت بدهیم، اعداد نسبت داده شده به یال‌ها متفاوت باشند.( $1 \leq a_i \leq e \quad , \quad a_i \in N$)

شرط لازم و کافی را برای $m$ و $n$ پیدا کنید به‌طوری که دنباله‌ی خوبی برای گراف $K_{m,n}$ وجود داشته باشد.

پاسخ


ابزار صفحه