المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:تئوری:سوال ۱۹

همبندی

دنباله‌ی درجات یک گراف ‎$n$‎ رأسی ‎$\langle d_1‎, ‎d_2‎, ‎\dots‎, ‎d_n\rangle$‎ است (نه لزوماً صعودی یا نزولی) و برای هر ‎$1 \le i < n$‎ داریم: ‎$$Max(d_i‎, ‎i-1)‎ + ‎d_{i+1} \geq n-1$$‎ ثابت کنید که این گراف همبند است.


ابزار صفحه