سوال ۲۸
در شکل روبهرو میخواهیم با پیمودن کوتاهترین مسیر روی خطوط شبکه، از نقطهی A به نقطهی B برویم. این کار بهچند طریق امکان پذیر است؟
۱۰
۲۸
۳۲
۴۴
۵۶
پاسخ
گزینه (۵) درست است.
بعضی از خطوط شبکه اضافه بوده و هرگز از آنها نمیتوان عبور کرد. با حذف آن خطوط٬ شبکهی جدید به صورت زیر در میآیند:
تعداد مسیرهای مطلوب در شبکهی فوق با تعداد مسیرهای از A به B در شبکهی زیر تفاوتی ندارد که این تعداد برابر \binom{3+5}{3}؛ یعنی ۵۶ میباشد.