Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

چه خوب

گراف G وتطابق ماکسیمال M در آن را در نظر بگیرید. X را مجموعه‌ای از مسیرهای افزایشی مجزا و به طول ۳، در G در نظر بگیرید که ماکسیمال هم باشد( یعنی مسیر افزایشی دیگری به طول ۳ نمی‌توان به آن اضافه کرد). اگر Max یک تطابق ماکسیمال در G باشد، ثابت کنید:

|M|+|X|23|Max|


ابزار صفحه