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

تعداد دورها توی گراف چند بخشی کامل k3,3 مثلن چطوریه ؟

سلام. عنوان ارسالتون رو ویرایش کردم. تعداد دورتا برابر میشه با مجموع دورهای بطول 4 و 6 و 8 و ... و 2n. چون برای گرافهای دوبخشی طول دور زوجه. حالا برای انتخاب یه دور بطول مثلاً 2k باید k راس از یک بخش و k راس از بخش دیگه انتخاب کنیم و به شکل درست(!) جایگشت بدیم. تعداد حالت تشکیل یک دور میشه [tex]\frac{(k-1)!\times k!}{2}[/tex]. یعنی یک راس رو ثابت میگیریم و بقیه رو میچینیم. چون جهت مهم نیست یه تقسیم بر 2 هم نیاز داره. پس جواب مسئلمون برای 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].