Изменения

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

|id = max_spanning_tree

#Докажем для остальных ребер. '''(рис.5)''' <br>Возьмем ребро, которое не лежит на диаметре окружности. В данном остовном дереве есть ребро, которое имеет такую же длину дуги. Ориентируем данные ребра в сторону часовой стрелки. Чтобы повороты этих ребер совпали, нужно, чтобы совпали их начала и концы. Покажем, что их начала никогда не совпадут. Чтобы начало первого ребра совпало с началом второго, нужно первое ребро повернуть хотя бы на половину длины окружности, то есть на <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> поворотов может не хватить для совпадения ребер.

[[Файл:Max spanning tree4.png|thumb|300px|center|Рис.5 Черным цветом выделены рассматриваемые ребра]]

==См. также==

*[[Остовные деревья: определения, лемма о безопасном ребре]]

*[[Остовное дерево в планарном графе]]

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Остовные деревья]]

[[Категория: Построение остовных деревьев]]