Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

گراف ‎G‎ با بزرگ‌ترین درجه‌ی ‎Δ‎ داده شده است. زیرگراف ‎H‎ از ‎G‎ دارای این خاصیت است که اگر بین دو رأس ‎u‎ و ‎v‎ در گراف ‎G‎ مسیری به طول ‎k‎ وجود داشته باشد، بین این دو رأس در ‎H‎ مسیری به طول حداکثر ‎2k‎ وجود دارد. ثابت کنید که بزرگترین درجه‌ی رئوس در ‎H‎ حداقل ‎Δ‎ است.


ابزار صفحه