Изменения
Нет описания правки
==Максимальное количество попарно непересекающихся остовных деревьев в графе с n вершинами==
{{Утверждение
|id = max_spanning_tree
|statement=Максимальное количество попарно непересекающихся [[Остовные деревья: определения, лемма о безопасном ребре#spanning_tree| остовных деревьев]] в графе с <tex>n</tex> вершинами равно <tex> \left \lfloor {\dfrac{n}{2}}\right \rfloor </tex> }}==Доказательство=|proof =
Очевидно, что наибольшее количество непересекающихся остовных деревьев может быть только в полном графе из <tex>n</tex> вершин. Количество ребер в таком графе равно <tex> \dfrac{n(n - 1)}{2}</tex>, а в каждом дереве <tex>n -
1</tex> ребро. Значит, в полном графе мы сможем построить не более <tex> \left \lfloor {\dfrac{n(n - 1)}{2(n - 1)}}\right \rfloor =</tex> <tex dpi = "130">\left \lfloor {\dfrac{n}{2}}\right \rfloor</tex> остовных деревьев.
===Описание алгоритма===
Расположим вершины на окружности так, чтобы они образовывали правильный многоугольник, и выберем начальную вершину '''(рис.1)'''. Для <tex>\left \lfloor {\dfrac{n}{2}}\right \rfloor</tex> вершин по часовой стрелке, начиная с этой вершины, будем строить остовные деревья. Для <tex>i</tex>-ой вершины строим такой путь <tex>:</tex><tex>V_i V_{i+1} V_{i-1} V_{i+2} V_{i-2}\ldots, </tex> {{---}} до тех пор, пока не соединим все вершины. Это и будет остовным деревом. '''(рис.2-3)'''
