المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۷

یک درخت وز‌ن‌دار $T$ با راس‌های ۱ تا $n$ داریم.

یک گراف $c$- رنگ‌پذیر $H$ با راس‌های ۱ تا $n$ داریم.

ثابت کنید افرازی از راس‌های ۱ تا $n$ به $k$ مجموعه با شرایط زیر وجود دارد:

  1. هیچ یالی از $H$ وجود نداشته باشد که هر دو سرش در یک مجموعه باشد.
  2. اگر مجموع وزن یال‌های $T$ را $X$ و مجموع وزن یال‌های $T$ که هر دو سرشان در یک مجموعه است را $Y$ بنامیم داشته باشیم $2\times Y \times c \geq X$.

ابزار صفحه