1. مسئله: در یک گراف کامل، رابطه 78 = p + q بین مرتبه (p) و اندازه (q) برقرار است. حداقل چند یال باید از این گراف برداشته شود تا گراف به دو گراف کامل تبدیل شود؟ 2. فرمول‌ها و نکات مهم: - در گراف کامل با مرتبه $p$، تعداد یال‌ها برابر است با $$q = \frac{p(p-1)}{2}$$ - در مسئله داده شده: $$p + q = 78$$ - هدف: حداقل تعداد یال‌هایی که باید برداشته شوند تا گراف به دو گراف کامل تقسیم شود. 3. حل مسئله: - ابتدا مقدار $p$ را پیدا می‌کنیم. از رابطه: $$p + \frac{p(p-1)}{2} = 78$$ $$2p + p(p-1) = 156$$ $$p^2 + p - 156 = 0$$ - معادله درجه دوم را حل می‌کنیم: $$p = \frac{-1 \pm \sqrt{1 + 4 \times 156}}{2} = \frac{-1 \pm \sqrt{625}}{2} = \frac{-1 \pm 25}{2}$$ - جواب مثبت: $$p = \frac{24}{2} = 12$$ - پس گراف کامل با 12 راس است و تعداد یال‌ها: $$q = \frac{12 \times 11}{2} = 66$$ 4. حال می‌خواهیم گراف را به دو گراف کامل تقسیم کنیم. فرض کنیم دو گراف کامل با $k$ و $12-k$ راس داریم. - تعداد یال‌های دو گراف کامل: $$q_1 = \frac{k(k-1)}{2}, \quad q_2 = \frac{(12-k)(11-k)}{2}$$ - تعداد یال‌های حذف شده: $$r = 66 - (q_1 + q_2)$$ 5. برای حداقل $r$، باید $k$ را طوری انتخاب کنیم که $q_1 + q_2$ بیشینه شود. - محاسبه برای $k=6$: $$q_1 = \frac{6 \times 5}{2} = 15$$ $$q_2 = \frac{6 \times 5}{2} = 15$$ $$r = 66 - (15 + 15) = 66 - 30 = 36$$ 6. بنابراین حداقل تعداد یال‌هایی که باید برداشته شود 36 است. پاسخ نهایی: 36