المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۱۴ و ۱۵

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

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

سوال ۱۴

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

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

پاسخ

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

سوال ۱۵

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

  1. 901
  2. 401
  3. 301
  4. 292
  5. 405

پاسخ

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


ابزار صفحه