سوال ۱۴
گراف شکل زیر از ۱۰ رأس و ۱۱ یال تشکیل شده است. می خواهیم روی تعدادی از رأس های این گراف خانه بسازیم به شرطی که اولا هیچ دو خانه ای مجاور نباشند (با یک یال مستقیما به هم متصل نباشند) ؛ ثانیا پس از پایان کار٬ در هیچ یک از رأس های خالی نتوان با رعایت شرط اول خانه‌ي جدیدی ساخت.
به چند روش می توان این کار را انجام داد؟ یکی از این روش های خانه سازی در شکل سمت چپ نمایش داده شده است.
- ۱۷
- ۲۴
- ۱۱
- ۲۷
- ۱۵
پاسخ
گزینه‌ی «۵» درست است.
در این سوال راهی نداریم جز شمارش تمام حالت های مسئله. می‌توانیم این‌گونه حالت بندی کنیم که اگر در یکی از دو رأس وسطی خانه باشد در این صورت 8 حالت برای پر کردن بقیه راس ها داریم. حال اگر در هیچ کدام از دورأس وسطی خانه نباشد نیز به 7 طریق می‌توان جدول را پر کرد. پس تعداد کل حالت ها برابر 15 است.