سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:تئوری نهایی سوم:سوال ۳
سوال ۳
یک گراف ساده‌ی $G$ داریم. می‌خواهیم به هر یال مانند $e$، یک عدد حقیقی مانند $f(e)$ نسبت دهیم، طوری که شروط زیر برقرار باشد:
- برای هر یال مانند $e$ داشته باشم: $0 \leq f(e) \leq 1$.
- مجموع اعداد یال‌های متصل به هر رأس، حداکثر ۱ باشد.
بیشینه‌ی ممکن مجموع اعداد یال‌های $G$ را، $max(G)$ می‌نامیم. حال هر یک از قسمت‌های زیر را حل کنید.
- ثابت کنید اگر گراف داده شده، دوبخشی باشد، می‌توان به هر یال، یکی از اعداد ۰ و ۱ را نسبت داد، طوری که مجموع اعداد یال‌های $G$، برابر $max(G)$ شود.
- ثابت کنید اگر گراف داده شده، دور زوج نداشته باشد، می‌توان به هر یال، یکی از اعداد ۰ و $\frac{1}{2}$ و ۱ را نسبت داد، طوری که مجموع اعداد یال‌های $G$، برابر $max(G)$ شود.
- ثابت کنید برای هر گراف داده شده، می‌توان به هر یال، یکی از اعداد ۰ و $\frac{1}{2}$ و ۱ را نسبت داد، مجموع اعداد یال‌های $G$، برابر $max(G)$ شود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
