المپدیا

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

ابزار کاربر

ابزار سایت


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

راه طولانی

فرض کنید $G$ گرافی ۲-همبند باشد با بیش از دو راس و $x,y \in V(G)$ و همه‌ی راس‌ها به جز $x$ و $y$ درجه‌ای ناکم‌تر از $k$‌ دارند. اثبات کنید در $G$ مسیری به طول حداقل $k$ که از دو طرف به $x$ و $y$ ختم می‌شود وجود دارد.


ابزار صفحه