Изменения
Нет описания правки
1</tex> ребро. Значит, в полном графе мы сможем построить не более <tex> \dfrac{n(n - 1)}{2(n - 1)} = \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)'''.
#Докажем, что построенные с помощью такого алгоритма остовные деревья будут попарно непересекающимися. Для этого докажем, что никакие ребра не совпадут. Ребра могут совпасть только в том случае, если дуги, на которые эти ребра опираются, будут одинаковой длины. Заметим также, что каждое следующее остовное дерево является поворотом при построении каждого последующего дерева его ребра получаются из поворотов ребер предыдущегона длину <tex> \dfrac{l}{n}</tex>, где <tex>l</tex> {{---}} длина окружности. Рассмотрим первое построенное остовное дерево '''(рис.3)''' В нем не более <tex>2</tex>-х ребер имеют одинаковую длину дуги (длина дуги у ребра, расположенного на диаметре окружности, не совпадает с длиной дуги любого другого ребра данного остовного дерева). Значит, повороты только этих ребер могут совпасть между собой. А чтобы они совпали, помимо одинаковых длин дуг у них должны совпасть концы. Покажем, что такого не произойдет.##Докажем, что повороты ребра, расположенного на диаметре окружности, не совпадут друг с другом (если <tex>n</tex> нечетно, то такого ребра не будет). Чтобы хоть какой-то поворот совпал, мы должны повернуть ребро на <tex>180 ^{\circ}</tex>. Каждый раз мы поворачиваем ребро на <tex>\dfrac{360 ^{\circ}}{n}</tex>. А так как мы поворачиваем ребро <tex>\dfrac{n}{2} - 1</tex> раз, то в сумме мы повернем его на <tex>\dfrac{360 ^{\circ}}{n}</tex> <tex dpi = "200">(</tex><tex>\dfrac{n}{2} - 1 </tex><tex dpi = "200">)</tex> <tex>=180 ^{\circ} - \dfrac{360 ^{\circ}}{n} < 180 ^{\circ}</tex>. А это значит, что никакие ребра не совпадут друг с другом.'''(рис.4)'''##Докажем для остальных ребер. '''(рис.5)''' Возьмем ребро, которое не лежит на диаметре окружности. В данном остовном дереве есть ребро, которое имеет такую же длину дуги. Ориентируем данные ребра в сторону часовой стрелки. Чтобы повороты этих ребер совпали, нужно, чтобы совпали их начала и концы. Покажем, что их начала никогда не совпадут. Чтобы начало первого ребра совпало с началом второго, нужно первое ребро повернуть хотя бы на половину длины окружности, то есть на <tex> \dfrac{l}{2}</tex>. Для этого нам нужно сделать <tex> \dfrac{n}{2} </tex> поворотов: <tex> \dfrac{l}{n} \cdot \dfrac{n}{2} = \dfrac{l}{2}</tex>. Но мы делаем только <tex> \dfrac{n}{2} - 1</tex> поворот. Для нечетных <tex>n</tex> граф будет неполным, поэтому даже <tex> \dfrac{n}{2}</tex> поворотов может не хватить для совпадения ребер.
}}
