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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
(не показаны 23 промежуточные версии 5 участников)
Строка 1: Строка 1:
 +
==Попарно непересекающиеся остовные деревья==
 
{{Утверждение
 
{{Утверждение
|id = max_spanning_tree
+
|id = max_spanning_tree                                                                                                                        
|statement=Максимальное количество попарно непересекающихся [[Остовные деревья: определения, лемма о безопасном ребре#spanning_tree| остовных деревьев]]  в графе с <tex>n</tex> вершинами равно <tex> \left \lfloor {\dfrac{n}{2}}\right \rfloor </tex>
+
|statement=Максимальное количество попарно непересекающихся [[Остовные деревья: определения, лемма о безопасном ребре#spanning_tree| остовных деревьев]]  в графе с <tex>n</tex> вершинами не более <tex> \left \lfloor {\dfrac{n}{2}}\right \rfloor </tex>  
|proof =  
+
|proof =                                                                                                                                                                                              
#Очевидно, что наибольшее количество непересекающихся остовных деревьев может быть только в полном графе из <tex>n</tex> вершин. Количество ребер в таком графе равно <tex> \dfrac{n(n - 1)}{2}</tex>, а в каждом дереве <tex>n -
+
Очевидно, что среди графов с <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> ребро. Значит, в полном графе мы сможем построить не более <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)'''.
+
}}
#Докажем, что построенные с помощью такого алгоритма остовные деревья будут попарно непересекающимися. Для этого докажем, что никакие ребра не совпадут. Ребра могут совпасть только в том случае, если дуги, на которые эти ребра опираются, будут одинаковой длины. Заметим, что при построении каждого последующего дерева его ребра получаются из поворотов ребер предыдущего на длину <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> поворотов может не хватить для совпадения ребер.
 
  
}}
+
==Построение==                                                                                                       
 +
===Описание алгоритма===                                                                                                                           
 +
Расположим вершины на окружности так, чтобы они являлись вершинами правильного многоугольника, и выберем начальную вершину (рис.<tex>1</tex>). Для <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> {{---}} до тех пор, пока не соединим все вершины. Это и будет остовным деревом. (рис.<tex>2-3</tex>)                                                                                                     
 +
{| cellpadding="10"                                                                                             
 +
|-                                                                                                                 
 +
|[[Файл:Max spanning tree1.png|thumb|300px|center|Рис.1 Стрелкой указана начальная вершина]] || [[Файл:Max spanning tree2.png|thumb|339px|center|Рис.2 Красным цветом выделено первое построенное остовное дерево]] || [[Файл:Max spanning tree6.png|thumb|270px|center|Рис.3 Все остовные деревья]]                                                         
 +
|}
 +
 
 +
===Доказательство корректности===                                                                                                                                                                         
 +
[[Файл:Max spanning tree3.png|thumb|250px|right|Рис.4 Черным цветом выделено рассматриваемое ребро, красным - все его повороты]] [[Файл:Max spanning tree4.png|thumb|250px|right|Рис.5 Черным цветом выделены рассматриваемые ребра, красным - остальные ребра остовного дерева]]Докажем, что построенные с помощью такого алгоритма остовные деревья будут попарно непересекающимися. Для этого докажем, что никакие ребра не совпадут. Ребра могут совпасть только в том случае, если дуги, на которые эти ребра опираются, будут одинаковой длины. Заметим, что при построении каждого последующего дерева его ребра получаются из поворотов ребер предыдущего на длину <tex> \dfrac{l}{n}</tex>, где <tex>l</tex> {{---}} длина окружности.                              Рассмотрим первое построенное остовное дерево.(рис.<tex>3</tex>) В нем не более <tex>2</tex>-х ребер имеют одинаковую длину дуги (длина дуги у ребра, расположенного на диаметре окружности, не совпадает с длиной дуги любого другого ребра данного остовного дерева). Значит, повороты только этих ребер могут совпасть между собой.                     
 +
#Докажем, что повороты ребра, расположенного на диаметре окружности, не совпадут друг с другом (если <tex>n</tex> нечетно, то такого ребра не будет).<br> Чтобы хоть какой-то поворот совпал, мы должны повернуть ребро на <tex>180 ^{\circ}</tex>. Каждый раз мы поворачиваем ребро на <tex>\dfrac{360 ^{\circ}}{n}</tex>. А так как мы поворачиваем ребро не более чем <tex>\dfrac{n}{2} - 1</tex> раз, то в сумме мы повернем его на <br> <tex>\dfrac{360 ^{\circ}}{n} \cdot</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>. А это значит, что никакие ребра не совпадут друг с другом. (рис.<tex>4</tex>)
 +
#Докажем для остальных ребер. (рис.<tex>5</tex>) <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> поворотов может не хватить для совпадения ребер.
  
 +
==См. также==                                                                                                       
 +
*[[Остовные деревья: определения, лемма о безопасном ребре]]                                                       
 +
*[[Остовное дерево в планарном графе]]                                                                                                                                                     
 +
*[[Минимально узкое остовное дерево]]                                                                                                                       
  
[[Категория: Алгоритмы и структуры данных]]  
+
==Источники информации==
[[Категория: Остовные деревья]]
+
*Карпов Д. В. {{---}} Теория графов, стр 297
 +
                                                                             
 +
[[Категория: Алгоритмы и структуры данных]]                                                                          
 +
[[Категория: Остовные деревья]]                                                                                      
 
[[Категория: Построение остовных деревьев]]
 
[[Категория: Построение остовных деревьев]]

Версия 00:51, 17 декабря 2017

Попарно непересекающиеся остовные деревья

Утверждение:
Максимальное количество попарно непересекающихся остовных деревьев в графе с [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] \left \lfloor {\dfrac{n(n - 1)}{2(n - 1)}}\right \rfloor =[/math] [math]\left \lfloor {\dfrac{n}{2}}\right \rfloor[/math] остовных деревьев.
[math]\triangleleft[/math]

Построение

Описание алгоритма

Расположим вершины на окружности так, чтобы они являлись вершинами правильного многоугольника, и выберем начальную вершину (рис.[math]1[/math]). Для [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] — до тех пор, пока не соединим все вершины. Это и будет остовным деревом. (рис.[math]2-3[/math])

Рис.1 Стрелкой указана начальная вершина
Рис.2 Красным цветом выделено первое построенное остовное дерево
Рис.3 Все остовные деревья

Доказательство корректности

Рис.4 Черным цветом выделено рассматриваемое ребро, красным - все его повороты
Рис.5 Черным цветом выделены рассматриваемые ребра, красным - остальные ребра остовного дерева
Докажем, что построенные с помощью такого алгоритма остовные деревья будут попарно непересекающимися. Для этого докажем, что никакие ребра не совпадут. Ребра могут совпасть только в том случае, если дуги, на которые эти ребра опираются, будут одинаковой длины. Заметим, что при построении каждого последующего дерева его ребра получаются из поворотов ребер предыдущего на длину [math] \dfrac{l}{n}[/math], где [math]l[/math] — длина окружности. Рассмотрим первое построенное остовное дерево.(рис.[math]3[/math]) В нем не более [math]2[/math]-х ребер имеют одинаковую длину дуги (длина дуги у ребра, расположенного на диаметре окружности, не совпадает с длиной дуги любого другого ребра данного остовного дерева). Значит, повороты только этих ребер могут совпасть между собой.
  1. Докажем, что повороты ребра, расположенного на диаметре окружности, не совпадут друг с другом (если [math]n[/math] нечетно, то такого ребра не будет).
    Чтобы хоть какой-то поворот совпал, мы должны повернуть ребро на [math]180 ^{\circ}[/math]. Каждый раз мы поворачиваем ребро на [math]\dfrac{360 ^{\circ}}{n}[/math]. А так как мы поворачиваем ребро не более чем [math]\dfrac{n}{2} - 1[/math] раз, то в сумме мы повернем его на
    [math]\dfrac{360 ^{\circ}}{n} \cdot[/math] [math]([/math][math]\dfrac{n}{2} - 1 [/math][math])[/math] [math]=180 ^{\circ} - \dfrac{360 ^{\circ}}{n} \lt 180 ^{\circ}[/math]. А это значит, что никакие ребра не совпадут друг с другом. (рис.[math]4[/math])
  2. Докажем для остальных ребер. (рис.[math]5[/math])
    Возьмем ребро, которое не лежит на диаметре окружности. В данном остовном дереве есть ребро, которое имеет такую же длину дуги. Ориентируем данные ребра в сторону часовой стрелки. Чтобы повороты этих ребер совпали, нужно, чтобы совпали их начала и концы. Покажем, что их начала никогда не совпадут. Чтобы начало первого ребра совпало с началом второго, нужно первое ребро повернуть хотя бы на половину длины окружности, то есть на [math] \dfrac{l}{2}[/math]. Для этого нам нужно сделать [math] \dfrac{n}{2} [/math] поворотов: [math] \dfrac{l}{n} \cdot \dfrac{n}{2} = \dfrac{l}{2}[/math]. Но мы делаем только [math] \dfrac{n}{2} - 1[/math] поворот. Аналогично с поворотом второго ребра. Для нечетных [math]n[/math] граф будет неполным, поэтому даже [math] \dfrac{n}{2}[/math] поворотов может не хватить для совпадения ребер.

См. также

Источники информации

  • Карпов Д. В. — Теория графов, стр 297