Викиконспекты - Вклад участника [ru]

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

2017-12-14T18:13:03Z

176.59.12.47:

{{Утверждение
|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> \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> поворотов может не хватить для совпадения ребер.

}}

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

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

2017-12-14T18:12:34Z

176.59.12.47:

{{Утверждение
|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> \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> поворотов может не хватить для совпадения ребер.

}}

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