چنانچه محفل ریاضی را سودمند یافتید، لطفا برای حمایت از ما به کانال تلگرامی محفل ریاضی بپیوندید!
به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
287 بازدید
سوال شده در دبیرستان و دانشگاه توسط OXIDE
ویرایش شده توسط OXIDE

ثابت کنید گراف های دو بخشی دور به طول فرد ندارند و تعداد دور به طول $2k$ در گراف کامل دو بخشی برابر است با: enter image description here

که در آن $m, n$ تعداد راس در هر بخش است.

دارای دیدگاه توسط erfanm
+2
منظورتون گراف کامل دو بخشی بود؟
دارای دیدگاه توسط OXIDE
+1
گراف کامل دو بخشی برای دور زوج و کلا گراف دو بخشی برای دور فرد
دارای دیدگاه توسط erfanm
+2
پس لطفا سوالتون رو ویرایش کنید.

1 پاسخ

+2 امتیاز
پاسخ داده شده توسط erfanm
انتخاب شده توسط AmirHosein
 
بهترین پاسخ

نشان میدهیم اگر گراف $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)! $$

لطفا ما را در شبکه های اجتماعی دنبال کنید:
به محفل ریاضی ایرانیان خوش آمدید!
امروز : تاریخ شمسی اینجا نمایش داده می‌شود

♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
60 نفر آنلاین
0 عضو و 60 مهمان در سایت حاضرند
بازدید امروز: 3233
بازدید دیروز: 6817
بازدید کل: 4712374
...