المپدیا

ابتدا مثالی ارائه دهید که تعداد مسیر‌های ۳-گریز آن از $O(n\sqrt{n})$ باشد.

فرض کنید در مثال ارائه شده، طول بلند‌ترین مسیر از $O(f(n))$ باشد. در این صورت می‌دانیم حداقل $O(f(n))$ مسیر ۳-گریز داریم. در نتیجه، تلاش کنید طول بلند‌ترین مسیر مثال مورد نظرتان کوتاه باشد.

اگر درجه‌ی راس $v$ در این درخت از $O(f(n))$ باشد،‌ تعداد مسیر‌های به طول ۲ که راس میانی آن‌ها $v$ است از $O(f(n)^2)$ خواهد بود. پس سعی کنید درجه‌ی راس‌ها را در مثال زیاد بزرگ نکنید.

راس $v$ را ریشه در نظر گیرید و $O(\sqrt{n})$ فرزند برای آن در نظر بگیرید. آن‌ها را $u_1, u_2, ..., u_l$ می‌نامیم.

برای هر یک از این فرزندان، یک فرزند قرار دهید. آن‌ها را $w_1, w_2, ..., w_l$ نامیم.

به هر یک از $w_i$ ها، از ‌$O(\sqrt{n})$ فرزند متصل کنید. تعداد مسیر‌های ۳-گریز درخت را بشمارید.

حال به سراغ اثبات $f(n) \in \Omega (n\sqrt{n})$ می‌رویم. اگر برگی پیدا کنیم که یک انتهای $\Omega(\sqrt{n})$ مسیر ۳-گریز باشد، چه کمکی به حل سوال می‌کند؟

در ادامه‌ی راهنمایی ۷ و در حالتی کلی‌تر، اگر با حذف $k$ راس از درخت، همبندی درخت حفظ شود و $ck\sqrt{n}$ مسیر ۳-گریز شمرده شود ($c$ ثابت است) و از گراف حذف شود، به کمک استقرا می‌توان حکم مورد نظر را اثبات کرد؟

حال می‌بایست آن $k$ راس را بیابیم. برگ $v$ را در نظر گیرید. چه زمانی $v$ همان راسی‌ است که با حذف آن به خواسته‌ی راهنمایی ۸ دست می‌یابیم؟ در غیر این صورت به حذف پدر این راس فکر کنید. این راس‌ را $p$ می‌نامیم.

مساله را در دو حالت بررسی کنید. تعداد برگ‌های متصل به $p$، از $O(\sqrt{n})$ باشد و یا بیشتر باشد.

اگر تعداد برگ‌های متصل به $p$ بیش از $O(\sqrt{n})$ باشد،‌ تعداد مسیر‌های به طول دو میان این برگ‌ها را بشمارید.

اگر از $O(\sqrt{n})$ برگ به $p$ متصل باشد، با حذف $p$ و تمام برگ‌های متصل به $p$، نشان دهید از $\Omega{n}$ مسیر ۳-گریز حذف مي‌شود.