Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۲:تئوری مقدماتی اول:سوال ۳

سوال ۳

گراف ساده ‎G‎ را در نظر بگیرید که ماتریس مجاورت آن ‎A‎ است . ‎G‎ را خوب می‌نامیم اگر و تنها اگر عددی طبیعی مانند ‎k‎ موجود باشد که ‎Ak‎ ماتریسی باشد که همه‌ی درایه‌هایش ناصفر است. (راهنمایی: به ارتباط درایه‌های ‎Ak‎ با گشت‌های به طول ‎k‎ در گراف توجه کنید‎.)

  1. شرط لازم و کافی برای خوب بودن یک گراف معرفی کنید و ادعای خود را ثابت کنید‎.‎
  2. ثابت کنید اگر ‎ G‌‎گراف ‎n‎ راسی و خوب باشد، عدد طبیعی ‎k<2n‎ وجود دارد که همه‌ی درایه‌های ‎Ak‎ ناصفر باشند‎.

ابزار صفحه