Максимальное количество попарно непересекающихся остовных деревьев в графе с n вершинами

Утверждение:

Максимальное количество попарно непересекающихся остовных деревьев в графе с [math]n[/math] вершинами равно [math] \left \lfloor {\dfrac{n}{2}}\right \rfloor [/math]

[math]\triangleright[/math]

Очевидно, что наибольшее количество непересекающихся остовных деревьев может быть только в полном графе из [math]n[/math] вершин. Количество ребер в таком графе равно [math] \dfrac{n(n - 1)}{2}[/math], а в каждом дереве [math]n - 1[/math] ребро. Значит, в полном графе мы сможем построить не более [math] \dfrac{n(n - 1)}{2(n - 1)} = \left \lfloor {\dfrac{n}{2}}\right \rfloor[/math] остовных деревьев. Алгоритм построения остовных деревьев. Расположим вершины на окружности и выберем начальную вершину(рис.1). Для [math]\left \lfloor {\dfrac{n}{2}}\right \rfloor[/math] вершин по часовой стрелке, начиная с этой вершины, будем строить остовные деревья. Для [math]i[/math]-ой вершины строим такой путь [math]:[/math][math]V_i V_{i+1} V_{i-1} V_{i+2} V_{i-2}\ldots, [/math] — до тех пор, пока не соединим все вершины. Это и будет остовным деревом (рис.2). Докажем, что построенные с помощью такого алгоритма остовные деревья будут попарно непересекающимися. Для этого докажем, что никакие ребра не совпадут. Ребра могут совпасть только в том случае, если дуги, на которые эти ребра опираются, будут одинаковой длины. Заметим, что каждое следующее остовное дерево является поворотом предыдущего. Рассмотрим первое построенное остовное дерево (рис.3) В нем не более [math]2[/math]-х ребер имеют одинаковую длину дуги(длина дуги у ребра, расположенного на диагонали, не совпадает с длиной дуги любого другого ребра данного остовного дерева). Значит, повороты только этих ребер могут совпасть между собой.

[math]\triangleleft[/math]