المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

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


ابزار صفحه