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