Спрятать заложницу

Автор задачи: Ильгиз Якупов, разработчик: Владислав Власов

Нам дан полный граф, в котором необходимо выделить как можно больше реберно-непересекающихся остовных деревьев.

Сначала решим задачу для четного количества вершин. Всегда можно сделать $$$\frac{n}{2}$$$ деревьев. Больше нельзя, потому что в графе только $$$\frac{n(n-1)}{2}$$$ ребер, а каждое остовное дерево состоит в точности из $$$n - 1$$$ ребра. Докажем, что ровно столько выбрать можно.

Возьмем как базу граф двух вершин и единственное остовное дерево в нем, и научимся переходить от $$$n-2$$$ вершин к $$$n$$$, добавив в ответ вершины $$$u$$$ и $$$v$$$.

По нашему предположению есть $$$\frac{n-2}{2}$$$ остовов на исходных $$$n-2$$$ вершинах (без $$$u$$$ и $$$v$$$). Разобьем эти $$$n - 2$$$ вершины на группы $$$X$$$ и $$$Y$$$, по $$$\frac{n-2}{2}$$$ вершин в каждой. Обозначим за $$$X_i$$$ и $$$Y_i$$$ (пронумерованные в любом порядке) $$$i$$$-ю вершину в $$$X$$$ и $$$Y$$$ соответственно. Дополним $$$i$$$-й остов ребрами из $$$X_i$$$ в $$$u$$$ и из $$$Y_i$$$ в $$$v$$$, как раз количество остовов совпадает с размерами групп $$$\frac{n-2}{2}$$$. Теперь нам лишь нужно добавить одно новое дерево к нашему текущему ответу. Проведем все ребра $$$Y_i \to u$$$ для всех $$$i$$$, все ребра из $$$X_i$$$ в $$$v$$$ для всех $$$i$$$, и ровно еще одно ребро $$$u \to v$$$. Ни одно из этих ребер мы не использовали в предыдущих остовах, так что остовы по-прежнему реберно не пересекаются.

Интересно, что таким образом мы использовали все ребра дерева из четного количества вершин. Для нечетного же случая построим деревья на $$$n-1$$$ вершинах как описали выше, после чего добавим еще одну вершину. При построении мы использовали все ребра, кроме тех $$$n-1$$$, которые соединяют последнюю вершину с остальными. Ровно $$$\frac{n - 1}{2}$$$ из них мы проведем для дополнения всех построенных остовов, после чего у нас не останется ребер на новый.

Так как количество ребер в полном графе равно $$$\frac{n(n - 1)}{2}$$$, и нам нужно провести и вывести практически каждое из них, асимптотика решения $$$\mathcal{O}(n^2)$$$.