به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
298 بازدید
سوال شده در دبیرستان و دانشگاه توسط 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>


☑ راهنمایی بیشتر: راهنمای تایپ
تلگرام محفل ریاضی
45 نفر آنلاین
0 عضو و 45 مهمان در سایت حاضرند
بازدید امروز: 2151
بازدید دیروز: 4860
بازدید کل: 5007803
...