به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+2 امتیاز
139 بازدید
در دانشگاه توسط کیوان عباس زاده (2,001 امتیاز)
ویرایش شده توسط AmirHosein

ثابت کنید هر گراف $(p-1)$-منظم که دارای $2p$ گره است، تطابق (جورسازی) کامل دارد.

ویرایشگر: پرسش‌کننده توضیح بیشتری وارد نکرده‌است.

1 پاسخ

+2 امتیاز
توسط AmirHosein (11,167 امتیاز)
ویرایش شده توسط AmirHosein

پیش از هر چیزی توجه کنید که باید فرض $p\geq 2$ را بیفزائید. چون اگر $p=1$ آنگاه یک گراف دو گره‌ایِ بدون یال دارید که هیچ جورسازی‌ای ندارد چه برسد به اینکه جورسازی کاملی داشته‌باشد.

در حالی که گراف‌تان دوبخشی باشد روش دقیقا یکسانی با پاسخی که برای پرسش دیگرتان گذاشتم حکم‌تان را نتیجه می‌دهد (اینجا کلیک کنید). درجهٔ بیشینه‌تان که با درجهٔ همهٔ گره‌هایتان در اینجا برابر است، می‌شود $\Delta=p-1$. تعداد یال‌ها در اینجا به شما داده نشده‌است ولی از روی درجه‌ها و تعداد گره‌ها می‌توان آن را یافت.

$$\begin{align} & 2|E|=\sum_{v\in V}\deg (v)=\sum_{v\in V}(p-1)=(p-1)|V|=2p(p-1)\\ & \Longrightarrow |E|=\frac{2p(p-1)}{2}=p(p-1) \end{align}$$

با جایگذاری در فرمول $|K|\geq\frac{|E|}{\Delta}$ (که $|K|$ تعداد یال‌های جورسازی بیشینه است) داریم

$$|K|\geq\frac{p(p-1)}{p-1}=p$$

پس جورسازی بیشینه‌تان دست‌کم $p$ یال دارد و چون یال‌های یک جورسازی نباید در گره‌ای مشترک باشند پس $2p$ گرهٔ متمایز با این $p$ یال جور شده‌اند که یعنی همهٔ گره‌های گراف، پس این جورسازی، یک جورسازیِ کامل است.

این اثبات برای گراف‌های دوبخشی است چون از قضیهٔ Konig که برای گراف‌های دوبخشی است استفاده کرده‌ایم. برای $p=2,3$ گراف $2p$گره‌ایِ $(p-1)$-منظم، دوبخشی نیز می‌شود.


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...