Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

گراف دوبخشی داریم که هر بخش آن n راس دارد و درجه‌ی هر راس آن حداقل n2 است.

  1. نشان دهید اگر M تطابقی با کم‌تر از n یال باشد، نسبت به M یک مسیر افزایشی به طول حداکثر ۳ داریم.
  2. ثابت کنید برای 1kn، تعداد تطابق‌های k1 یالی حداکثر n2 برابر تعداد تطابق‌های k یالی است.

پاسخ


ابزار صفحه