المپدیا

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

ابزار کاربر

ابزار سایت


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

شرط برشی برای بحرانی رنگ‌پذیری

نشان دهید که اگر $G$ $-(k+1)$بحرانی باشد و $S\subseteq V(G)$ مجموعه‌ی جداکننده باشد، آن‌گاه تعداد مولفه‌های $G-S$ از تعداد حالات تقسیم کردن $|S|$ شیئی به حداکثر $k$ دسته بیش‌تر نیست.


ابزار صفحه