سوال ۱

گرافی که شرط مسئله را داشته باشد و بیشترین تعداد یال را داشته باشد در نظر بگیرید. آن را G می‌نامیم. روی G، الگوریتم $DFS$ را اجرا کنید.

برای تمیز‌نویسی بخش نهایی، اگر $3a=k$ می‌توانید از نامساوی زیر استفاده کنید $$e(G)=q\binom{k}{2} \ge \frac{n}{2k}\cdot \frac{k(k-1)}{2} = \frac{n(k-1)}{4}. $$

<راهنمایی> برای هر راس، حداکثر چند back-edge به سمت بالا از آن راس ممکن است وجود داشته باشد؟

فرض کنید back-edge هایی که از راس $v$ به بالا می‌روند، به ترتیب ارتفاع به رئوس $u_1, u_2, \dots, u_k$ بروند. همچنین طول کوتاه‌ترین و بلند‌ترین دور گراف را به ترتیب $l$ و $r$ بگیرید.

دقت کنید برای هر $i$ اختلاف ارتفاع $u_i$ و $u_{i+1}$ حداقل $l-2$ باید باشد.

در صورتی که گزاره‌ی راهنمایی فوق درست نباشد، می‌توانید دور کوتاه‌تر از طول $l$ بیابید.

اختلاف ارتفاع $u_1$ و $u_k$ حداکثر $r-2$ است.

تعداد back-edge های متصل به هر راس طبق استدلال‌های فوق حداکثر از $O(\frac{r}{l})$ خواهد بود.

برای مثال، تعدادی خوشه در نظر بگیرید.

در هر خوشه، $3a$ راس قرار دهید، راس‌های باقی‌مانده نیز مهم نیستند.

برای تمیز‌نویسی بخش نهایی، می‌توانید از نامساوی زیر استفاده کنید. در نظر بگیرید $k=3a$ \[ q=\left\lfloor \frac{n}{k}\right\rfloor \ge \frac{n}{2k}. \]

\[ e(G)=q\binom{k}{2} \ge \frac{n}{2k}\cdot \frac{k(k-1)}{2} = \frac{n(k-1)}{4}. \]