المپدیا

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

ابزار کاربر

ابزار سایت


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

جداسازی

گراف بدون جهت ‎$G$‎ با ‎$n^2$‎ راس به این صورت ساخته شده است که رئوسش دوتایی‌های ‎$(a,b)$‎ به ازای ‎$1 \leq a‎, ‎b \leq n$‎ می‌باشند. هر راس ‎$(a,b)$‎ به رئوس ‎$(a-1,b)‎, ‎(a+1,b)‎, ‎(a,b-1)‎, ‎(a,b+1)$ (در صورت وجود این رئوس) وصل است. یعنی درجه‌ی هر راس حداکثر ‎۴‎ خواهد شد. مجموعه‌ی ‎$S$‎ از رئوس داده شده است و می‌دانیم ‎$|S| < n^2/2$‎. ثابت کنید تعداد یال‌های بین مجموعه‌ی ‎$S$‎ و بقیه‌ی رئوس گراف ‎$\Omega(\sqrt{|S|})$‎ است.


ابزار صفحه