المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۲

یک نمایش ضربی با طول $k$ برای گراف $G$ عبارت است از تابعی مانند $p$ که به هر راس گراف $G$ یک $k$ - تایی مرتب از اعداد طبیعی را نسبت می‌دهد به‌طوری‌که دو راس $v_i$ و $v_j$ مجاورند اگر و تنها اگر برای هر $1\leq l \leq k$ و مولفه‌ها‌ی $l$- ام $p(v_i)$ و $p(v_j)$ متفاوت باشند. ثابت کنید هر گراف $n$ راسی $r$ - منتظم یک نمایش ضربی با طول $n-r$ دارد.


ابزار صفحه