تالار گفتمان مانشت

سوال تعداد مسیرها در یک گراف دوبخشی

تعداد مسیر ها به طول 4 به این صورت بدست می آید :

1. اگر راس ابتدا و انتها در نیمه هفت راسی باشد :
[tex]\binom{7}{2}×\binom{5}{1}×(3×2)=630[/tex]

2. اگر راس ابتدا و انتها در نیمه سه راسی باشد :
[tex]\binom{3}{2}×\binom{1}{1}×(7×6)=126[/tex]

جمع این دو برابر 756 است.

------------------
تعداد مسیر ها به طول 5 به این صورت بدست می آید :

راس ابتدا در یکی از نیمه ها و راس انتها در نیمه دیگر است پس یک حالت برای محاسبه وجود دارد که به صورت زیر است :

[tex](7×5×6)×(3×2×1)=1260[/tex]




بنابراین گزینه یک صحیح است.