سوال ۹
گراف ۲۰ راسی زیر با راس‌های $1, 2, \cdots , 20$ را در نظر بگیرید. به چند طریق می‌توان از این گراف تعدادی یال حذف کرد به طوری که گراف همبند بماند؟ توجه کنید یک حالت این است که هیچ یالی حذف نکنیم.
- $207391$
- $946025$
- $2 \times 4^{10}$
- $834261$
- $738634$
پاسخ
گزینه (۲) درست است.
$a_n$ را تعداد حالات خواسته شده برای یک گراف $2n$-راسی در نظر می‌گیریم. $b_n$ را نیز مانند $a_n$ تعریف می‌کنیم؛ با این تفاوت که از قبل بدانیم بین دو راس سمت چپ مسیری وجود داشته است. داریم:
$$a_n=3a_{n-1}+b_{n-1}$$
و
$$b_n=4a_{n-1}+2b_{n-1}$$
از روابط بازگشتی بالا مقدار $a_{10}$ که پاسخ مسئله است به‌دست می‌آید.