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

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

دنباله‌ی a1an از اعداد متفاوت را روی گراف G با n راس و e یال می‌گوییم خوب است، در صورتی که اگر به هر یال uv از G باقی‌مانده‌ی au+av بر e را نسبت بدهیم، اعداد نسبت داده شده به یال‌ها متفاوت باشند.( 1aie,aiN)

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

پاسخ


ابزار صفحه