فرض کنید یک جدول $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

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

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

• سوال قبل
• سوال بعد