ایلیچ به سربازی رفته و در همان روز اول از او خواسته اند تا برای مسئله ی زیر، الگوریتمی در زمان چندجمله‌ای ارائه کند:

گراف همبند $n$ رأسی و فاقد یال برشی $G$ به همراه زیردرخت فراگیر $T$ از آن، در ورودی داده می شود.تضمین می شود درجه ی هر رأس در $T$ حداکثر ۱۴۰۰ است و هم چنین به ازای هر یال $e$ از $G$ طول مسیر بین دو رأس انتهایی $e$ در $T$ حداکثر ۲۰۲۱ می باشد. هدف، یافتن زیرگرافی فراگیر و فاقد یال برشي از $G$ با تعداد یال های کمینه است.

به ایلیچ کمک کنید و الگوریتمی چندجمله ای برای مسئله ی بالا ارائه کنید، وگرنه وقتی از سربازی برگردد، خودتان می دانید …

• سوال قبل