تعداد دورها توی گراف چند بخشی کامل k3,3 مثلن چطوریه ؟
سلام. عنوان ارسالتون رو ویرایش کردم. تعداد دورتا برابر میشه با مجموع دورهای بطول ۴ و ۶ و ۸ و ... و ۲n. چون برای گرافهای دوبخشی طول دور زوجه. حالا برای انتخاب یه دور بطول مثلاً ۲k باید k راس از یک بخش و k راس از بخش دیگه انتخاب کنیم و به شکل درست(!) جایگشت بدیم. تعداد حالت تشکیل یک دور میشه [tex]\frac{(k-1)!\times k!}{2}[/tex]. یعنی یک راس رو ثابت میگیریم و بقیه رو میچینیم. چون جهت مهم نیست یه تقسیم بر ۲ هم نیاز داره. پس جواب مسئلمون برای Kn,n میشه [tex]\sum_{i=2}^n{\binom{n}{i}}^2\frac{i!\times(i-1)!}{2}[/tex] و برای حالت کلی گراف Km,n که m بزرگترمساوی n هست میشه [tex]\sum_{i=2}^n\binom{n}{i}\binom{m}{i}\frac{i!\times(i-1)!}{2}[/tex].