المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۰:تئوری:سوال ۴

مسطح وزن‌دار

گراف همبند و مسطح و وزن‌دار $G$ را در نظر بگیرید و گراف دوگان آن‌را $G'$ هم ‌وزن‌دار است و وزن هر یال از $G'$ برابر با وزن یال متناظرش در $G$ (یالی از $G$ که این یال را قطع می‌کند.) است.

درخت فراگیر کمینه در $G$ را $T$ بنامید. یال‌هایی از $G'$ را در نظر بگیرید که دوگان آن‌ها در $T$ قرار ندارد. ثابت کنید این یال‌ها درخت فراگیر بیشینه را در $G'$ تشکیل می‌دهند.

(دوگان یال $e$: اگر یال $e$ در $G$ بین سطوح $x$ و $y$ بود در $G'$ بین راس‌های متناظر $x$ و $y$ خواهد بود.)


ابزار صفحه