سوال تعداد مسیرها در یک گراف دوبخشی
تعداد مسیر ها به طول ۴ به این صورت بدست می آید :
۱/ اگر راس ابتدا و انتها در نیمه هفت راسی باشد :
[tex]\binom{7}{2}×\binom{5}{1}×(۳×۲)=۶۳۰[/tex]
۲/ اگر راس ابتدا و انتها در نیمه سه راسی باشد :
[tex]\binom{3}{2}×\binom{1}{1}×(۷×۶)=۱۲۶[/tex]
جمع این دو برابر ۷۵۶ است.
------------------
تعداد مسیر ها به طول ۵ به این صورت بدست می آید :
راس ابتدا در یکی از نیمه ها و راس انتها در نیمه دیگر است پس یک حالت برای محاسبه وجود دارد که به صورت زیر است :
[tex](7×۵×۶)×(۳×۲×۱)=۱۲۶۰[/tex]
بنابراین گزینه یک صحیح است.