المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۲۹:سوالات ۱۴ و ۱۵

سوالات ۱۴ و ۱۵

فرض کنید یک جدول $m \times n$ داریم. نقاط گوشه‌های مربع‌های واحد جدول را رأس و اضلاع آن‌ها را یال در نظر بگیرید؛ به این ترتیب یک گراف به دست می‌آید. برای مثال به ازای $m=3$ و $n=4$ گرافی با ۲۰ رأس و ۳۱~یال به شکل زیر به دست می‌آید:

به این گراف، گراف جدولی حاصل از یک جدول $m \times n$ گوییم. فرض کنید $G$ یک گراف جدولی و $T$ یک زیردرخت فراگیر از آن باشد. به ازای هر خانه از جدول، تعداد یال‌هایی از $T$ را که ضلع آن خانه هستند، استحکام آن خانه می‌نامیم.

سوال ۱۴

به ازای $m=10$ و $n=10$، کمینه‌ی مجموع استحکام خانه‌ها را در میان تمام زیردرخت‌های فراگیر ممکن بیابید.

  1. $240$
  2. $199$
  3. $120$
  4. $201$
  5. $139$

پاسخ

گزینه (۴) درست است.

سوال ۱۵

دوام هر خانه را مجذور استحکام آن (استحکام به توان دو) در نظر می‌گیریم. به ازای $m=10$ و $n=10$، کمینه‌ی مجموع دوام خانه‌ها را در میان تمام زیردرخت‌های فراگیر ممکن بیابید.

  1. ۴۰۵
  2. ۴۰۱
  3. ۳۰۱
  4. ۲۹۲
  5. ۹۰۱

پاسخ

گزینه (۱) درست است.


ابزار صفحه