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

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۸

ماشینی به نام WallE داریم که گراف G را به عنوان ورودی می‌گیرد و به هر راس ان یک عدد حقیقی از بازه‌ی [0,1] نسبت می‌دهد به طوری که مجموع اعداد نسبت داده شده به راس‌ها کمینه باشد و نیز به ازای هر یال (u,v) از G مجموع اعداد روی راس v و راس u برابر 1 باشد.

اکنون یک گراف G با 2×n راس که یک مجموعه مستقل n راسی دارد را به WallE داده‌ایم. با فرض این که مجموع اعدادی که WallE به راس‌ها نسبت داده است n باش ثابت کنید گراف G مچینگ (جورسازی) کامل دارد.


ابزار صفحه