المپدیا

به الگوریتم $BFS$ فکر کنید که از راس دلخواه $u$ شروع شده باشد. چه ساختاری به گراف تحت این الگوریتم داده می‌شود؟

اگر به نحو دیگری محدودیت سوال را بنگریم، قصد داریم تعدادی راس حذف کنیم به طوری که به ازای هر راس حذف شده، یک راس متناظر حذف نشده باقی مانده باشد.

راس‌ها را بر حسب فاصله‌ی آن‌ها از $u$، به تعدادی دسته افراز کنید. حال اگر قصد داشته باشیم $u$ را در گراف نگه‌داریم به نحوی که شرایط مسئله برای این راس خاص و راهنمایی دوم برای کل گراف پابرجا باشند،‌ کدام دسته را حذف کنیم؟

فرض کنید دسته‌های راهنمایی قبل را از نزدیک‌ترین تا دورترین نسبت به $u$ پیمایش کنیم. اگر به دسته‌ای رسیدیم که تعداد راس‌هایش کمتر یا مساوی با تمام دسته‌های قبلی بود، آیا می‌توانیم آن را حذف کنیم (به راهنمایی ۲ توجه کنید)؟ اگر بیشتر بود چه؟ اولین دسته‌ای که حذف می‌کنیم حداکثر چه فاصله‌ای از $u$ دارند؟

اگر این الگوریتم را پس از حذف دسته‌ی مورد نظر در راهنمایی ۴ از راس جدید و دیده نشده‌ی دیگری شروع کنیم، در نهایت حداکثر چند راس حذف خواهند شد؟

آیا پیچیدگی زمانی الگوریتم ارائه شده نسبت به $BFS$ تفاوتی دارد؟

اگر از بخش (آ) استفاده کنیم و مجموعه‌ای از راس‌ها را بدست آوریم، آیا می‌توان تمام آن‌ها را همرنگ کرد؟

اگر پس از اجرای هر بار الگوریتم از راس‌های رنگ‌شده صرف نظر کنیم، چند بار نیاز داریم الگوریتم بخش (آ) را اجرا کنیم تا تمام راس‌ها رنگ شوند؟

بنا بر دو راهنمایی قبل، راهی از $O((n+m)\log{n})$ یافته‌ایم. آیا می‌توان همین الگوریتم را بهبود بخشید تا به نمره‌ی کامل سوال دست یابیم؟

الگوریتم ارائه شده در بخش (آ) را دقیق‌تر تحلیل زمانی کنید.

آیا وقتی در الگوریتم بخش (آ) قصد حذف تعدادی از رئوس در گراف را داریم، روی خود آن‌ها $BFS$ اجرا می‌شود؟

اگر زمانی که تشخیص دادیم تعداد راس‌های یک دسته‌ در بخش (آ) به اندازه‌ی کافی کم است تا آن‌ها را حذف کنیم، دیگر $BFS$ را از آن راس‌ها ادامه ندهیم، از هر راس چند بار الگوریتم $BFS$ دیدن می‌کند؟ تحلیل زمانی الگوریتم جدید چه خواهد بود؟