برای چه عددهای طبیعیِ $n$ای یک گرافِ سه بخشیِ کامل که در هر بخشش $n$ گره دارد، دارای جورسازیِ کامل است؟

Question

متن درست پرسش: برای چه عددهای طبیعیِ $n$ای یک گرافِ سه‌بخشیِ کامل که در هر بخشش $n$ گره دارد، دارای جورسازیِ کامل (تطابق تام) است؟

متن نوشته‌شده بوسیلهٔ پرسش‌کننده: هایی n را بیابید که گراف سه بخشی کامل جورسازی (تطابق) تام داشته باشد.یا به بیان دیگر برای چه n هایی گراف سه بخشی کامل دارای جورسازی تام است؟

Comments

لطفا راهنمایی کنید

---

@Sh1292 اینجا مکانی برای یادگیری است نه برای رفع تکلیف یا پروژه. برای اینکه انگیزهٔ بیشتری برای کمک‌شدن ایجاد کنید تلاش خودتان را اشاره کنید. وظیفهٔ دیگران نیست که تکالیف ما را انجام بدهند. حتی اگر هم قضیهٔ فقط رفع تکلیف نباشد، باز هم نباید انتظار و تفکر وظیفه بودن نسبت به هر کسی غیر از خودمان داشته‌باشیم، دیگران در صورت داشتن دانش لازم، زمان کافی و تمایل حتما کمک خواهند کرد. شما زمان و دانش دیگران را نمی‌توانید تغییر دهید، تنها عامل آخر یعنی تمایل‌شان را می‌توانید افزایش دهید و آن هم با نشان دادن اینکه
۱- واقعا برای پرسش‌تان ارزش قائل بودید
۲- و نیت‌تان فقط تحویل دادن پاسخ در زمان تعیین شده برای کسب نمرده نبوده‌است
۳- و اینکه رویش فکر کرده‌اید و دست‌به‌قلم شده‌اید و نوشته‌اید و تعریف‌ها و درس قبل از این تمرین را خوانده‌اید
۴- همانطور که پاسخ‌دهنده برای نوشتن پاسخ‌تان زمان صرف می‌کند، شما هم برای نوشتن پرسش‌تان زمان صرف کرده‌اید و به آن نکشیده‌اید.
با این کارها می‌توانید انگیزه ایچاد کنید و گر نه دیدگاه گذاشتن که عجله دارم، نیاز دارم، تا فردا وقت دارم و از این قبیل، برعکس تأثیر منفی هم در انگیزه به پاسخ‌دادن ایجاد می‌کند.

---

این سوال جز تکلیف نبوده چون خیلی ذهنم درگیرش بود و از جواب خودم مطمئن نبودم پرسیدم ممنون از توجهتون

---

@Sh1292 تلاش خودتان را می‌توانید در ادامهٔ متن پرسش اشاره کنید.
متن پرسش خالی زمانی گذاشته می‌شود که هیچ چیزی غیر از جملهٔ متن پرسش را نمی‌دانید. اگر قصدتان این است که ببینید پاسخ‌تان درست یا خیر، باید پاسخ‌تان را به عنوان تلاش خودتان اشاره کنید تا درستی یا نادرستی آن چک شود. پست‌های زیادی در سایت هستند که حل خودشان را اشاره کرده‌اند و پرسیده‌اند که آیا درست پیش رفته‌اند یا در جایی خطا دارند، می‌توانید آنها را چک کنید تا در مورد ویرایش پرسش‌تان ایده بگیرید.
در ضمن قسمت «مرجع» را ویرایش کنید. آیا این نام یک کتاب است یا نام یک درس؟ نام درس، مبحث، مقطع یا کلاس مرجع محسوب نمی‌شود. مرجع یعنی کتاب یا مقاله که در آنجا بتوان پرسش شما را یافت. پست زیر را ببینید.
https://math.irancircle.com/11973

Answer 1

اگر واقعا تلاش می‌کردید و تلاش‌تان را می‌نوشتید، همان ۲ سال پیش پاسخ‌تان را می‌گرفتید. حتی متن پرسش را هم درست ننوشته‌اید! به هر حال صرفا برای کاربرهای دیگر که برای یادگیری به این سایت می‌آیند، پاسخ پرسش $n$های زوج است. فرض کنید $n=2k$ باشد، آنگاه یک جورسازیِ کامل برای گراف سه‌بخشی که هر سه بخشش دارای $n$ گره است به این شکل خواهدبود که $k$ گرهٔ نخستِ بخش یکُم را به $k$ گرهٔ نخستِ بخش دوم، و $k$ گرهٔ دوم بخش یکُم را به $k$ گرهٔ نخست بخش سوم نظیر به نظیر جفت کنید. در پایان $k$ گرهٔ دوم بخش دوم را به $k$ گرهٔ دوم بخش سوم نظیر به نظیر جفت کنید. به این ترتیب هر $3n$ گرهٔ گراف پوشش داده می‌شود، پس جورسازی‌مان کامل (تام) است.

اکنون اگر $n$ فرد باشد، ثابت می‌کنیم که هیچ جورسازیِ کاملی برای گراف‌مان وجود ندارد. تعدادِ گره‌هایی از بخش یکُم که با گره‌هایی از بخش دوم جفت شده‌اند را با $r$ و تعدادِ گره‌هایی از بخش یکُم که با گره‌هایی از بخش سوم جفت شده‌اند را با $s$ نشان دهید. پس داریم $r+s=n$. از آنجا که $n$ فرد است، باید یکی از $r$ و $s$ فرد و دیگری زوج باشد. بدون کاستن از کلیت (حداکثر با تغییر ترتیب بخش دوم و سوم) فرض کنید $r$ فرد است. اکنون $n-r=s$ گره از بخش دوم و $n-s=r$ گره از بخش سوم باقی مانده‌اند که باید آنها را پوشش دهیم. چون بخش یکُم کامل استفاده شده‌است، پس این $s$ گره از بخش دوم باید با $r$ گره از بخش سوم جفت شوند ولی این امکان‌پذیر نیست زیرا $s$ زوج و $r$ فرد است، در نتیجه دو عدد متفاوت هستند و در بهترین حالت یک گره تنها بدون جفت خواهد ماند. این ثابت می‌کند که هیچ جورسازیِ کاملی برای یک گراف سه‌بخشی با تعداد گره‌های برابر در هر بخش که این تعداد فرد باشد (چه این گراف سه‌بخشی کامل باشد و یا کمتر یال داشته‌باشد) وجو ندارد.