مریم میخواهد از بالاترین رأسِ گراف جهتدار زیر به پایینترین رأس آن برود. او تنها میتواند در جهتِ مشخصشده روی یالها حرکت کند و نمیتواند از هیچ رأسی بیش از یک بار عبور نماید. مریم به چند روش میتواند این مسیر را بپیماید؟
پاسخ
گزینه (۲) درست است.
اگر دو یال ابتدای مسیر و سه یال انتهای مسیر را انتخاب کنیم، باقی مسیر به شکل یکتا مشخص میشود. یال اول مسیر سه حالت دارد و بعد از انتخاب یال اول، یال دوم نیز دو حالت دارد. بنابراین:
3×2=6
حالت برای دو یال اول مسیر وجود دارد.
یال آخر مسیر دو حالت دارد و مشابه انتخابهای قبل، پس از انتخاب یال آخر، یال یکی مانده به آخر نیز دو حالت دارد، و به طور مشابه یال دو تا مانده به آخر نیز پس از انتخاب دو یال آخر دو حالت دارد. بنابراین:
2×2×2=8
حالت برای سه یال آخر مسیر داریم.
بنابراین در مجموع:
3×2×2×2×2=48
حالت برای این کار موجود است.
.