چرا یک گراف دوبخشی هیچ دور به طول فرد ندارد؟ و تعداد دورهای با طول زوج در گراف دوبخشی کامل را بیابید.

Question

ثابت کنید گراف‌های دوبخشی، دور به طول فرد ندارند. و همینطور تعداد دور به طول $2k$ در یک گرافِ دوبخشیِ کاملِ $K_{m,n}$ که $m$ و $n$ تعداد گره‌ها در هر بخشِ آن است، برابر است با:

$$\binom{m}{k}\binom{n}{k}\frac{k!(k-1)!}{2}$$

Comments

منظورتون گراف کامل دو بخشی بود؟

---

گراف کامل دو بخشی برای دور زوج و کلا گراف دو بخشی برای دور فرد

---

پس لطفا سوالتون رو ویرایش کنید.

Answer 1

نشان میدهیم اگر گراف $G$ دو بخشی باشد آنگاه دارای دور فقط با طول زوج است. فرض کنید$G$ یک گراف دوبخشی با بخش های $W_{1}$و $W_{1}$باشد همچنین فرض کنید که $C=( v_{1} , v_{2} ,..., x_{n} , x_{1} )$ یک دور باشد.

$v_{1}$ یا در $W_{1}$ است یا در $W_{2}$ بدون کاستن از کلیت فرض کنید که در $W_{1}$ باشد طبق تعریف گراف دوبخشی باید $v_{2} \in W_{2}$ پس $v_{3} \in W_{1}$ و... دقت کنید اندیس های زوج در $W_{2}$ قرار می گیرند

چون $v_{1} \in W_{1}$ باید $v_{n} \in W_{2}$ و این بدین معنی است که $n$ زوج است.

همانطور که نشان داده شد برای هر دور نصف رئوس در $W_{1}$ و نصف دیگر در $W_{2}$ قرار دارند

حال اگر بخواهیم تعداد حالات دوری به طول $2k$ را بیابیم باید $k$ راس را از مجموعه اول و $k$تای دیگر را از مجموعه دوم انتخاب کنیم پس تا اینجای کار ${n \choose{k} }{m \choose{k} }$ حالت و اگر اولین عضو دور از مجموعه اول باشد (چون دور داریم با جایگشت دایره ای مواجه هستیم)$\frac{(k-1)!}{2}$ حالت داریم اما چون بین هر یک از این عناصر، عناصر مجموعه دوم قرار میگیرد لذا این عناصر $\frac{(k)!}{2}$ حالت قرار گیری دارند لذا تا اینجا تعداد حالات برابر شد با ${n \choose{k} }{m \choose{k} } \frac{(k-1)!}{2} \frac{(k)!}{2}$ همچنین اینکه اولین عضو از مجموعه اول باشد یا دوم خودش دو حالت است و با جایگذاری تعداد حالات برابر است با:

$${n \choose{k} }{m \choose{k} } \frac{(k-1)!}{2} (k)!$$