http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=176.59.13.228&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T22:48:04ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE_%D1%83%D0%B7%D0%BA%D0%BE%D0%B5_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=58893Минимально узкое остовное дерево2017-01-06T06:32:08Z<p>176.59.13.228: </p>
<hr />
<div>{{Утверждение<br />
|statement=Минимальное остовное дерево является minimum bottleneck spanning tree.<br />
|proof=Предположим, если минимальное остовное не является MBST, значит в графе существует набор ребер которые мы не взяли в наш остов, при замене на которые, наше дерево станет MBST. Так же рёбра вне остова должны быть меньше рёбер из остова, чтобы уменьшить минимальное максимально ребро. Но по определению MST, сумма рёбер дерева минимальна, значит вне остова нету рёбер с меньшим весом. Так как наше предположение неверно, MST является MBST.<br />
}}<br />
{{Утверждение<br />
|statement=Minimum bottleneck spanning tree не всегда является минимальным остовным деревом.<br />
|proof=Рассмотрим пример, где MBST не является минимальным остовным деревом:<br />
<div class="tleft" style="clear:none">[[Файл:MBST-example.png|left|thumb|250px|Пример MBST дерева.]]</div><br />
<div class="tleft" style="clear:none">[[Файл:MSTisMBST.png|left|thumb|250px|Пример MST дерева.]]</div><br />
<br />
}}<br />
{{Задача<br />
|definition=Проверка остовного дерева на MBST.<br />
}}<br />
<h4>Алгоритм</h4><br />
Если у нас получится соединить все вершины графа, используя рёбра меньше максимального из нашего остова, значит мы сможем построить другой остов, в котором максимальное ребро меньше нашего максимального. Для этого найдём максимальное ребро в нашем дереве. Соединим все вершины, между которыми рёбра с весом меньше максимального при помощи [[СНМ (наивные реализации)|СНМ]]. Если в результате у нас все вершины лежат в одном множестве, значит наше дерево не является MBST, иначе оно MBST.<br />
<h4>Асимптотика</h4><br />
Максимальное ребро мы ищем линейно за количество рёбер в дереве <tex>O(N)</tex>.<br>Работа с СНМ займет <tex>O(N\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит <tex>4</tex> во всех практических приложениях и которую можно принять за константу.<br>В результате получаем алгоритм работающий за линейное время <tex>O(N)</tex>.<br />
<h4>Псевдокод</h4><br />
<code><br />
'''function''' ifMBST():<br />
'''int''' united = 0, maxEdge = -Inf<br />
'''for''' i = 1 to tree.size<br />
maxEdge = max(maxEdge, tree[i].cost)<br />
'''for''' i = 1 to n<br />
'''if''' e[i].cost >= maxEdge<br />
'''continue'''<br />
'''if''' find(e[i].from]) != find(e[i].to)<br />
united++<br />
'''if''' united == e.size - 1<br />
'''return''' true<br />
'''else''' <br />
'''return''' false<br />
</code></div>176.59.13.228http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B9_%D0%A2%D0%B0%D1%80%D1%8C%D1%8F%D0%BD%D0%B0_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0&diff=58829Критерий Тарьяна минимальности остовного дерева2017-01-05T15:40:33Z<p>176.59.13.228: /* Уникальность остовного дерева */</p>
<hr />
<div>== Критерий Тарьяна ==<br />
{{Теорема<br />
|about=<br />
критерий Тарьяна минимальности остовного дерева<br />
|statement=<br />
Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево.<br />
|proof=<br />
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:<br />
если существует ребро, не максимальное на образовавшемся цикле, то мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.<br />
<br />
Теперь докажем, что дерево <tex>K</tex>, удовлетворяющее условию, минимально:<br />
<br />
{{Утверждение<br />
|statement=Для любого разреза <tex>\langle S, T \rangle</tex>, в котором ребро <tex>uv</tex> {{---}} единственное, пересекающее его в <tex>K</tex>, вес этого ребра минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез.<br />
<br />
|proof=Рассмотрим ребро <tex>ab \notin K</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>K</tex>.<br />
По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути.<br />
При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез.<br />
Но единственное такое ребро в остовном дереве {{---}} это <tex>uv</tex>.<br />
Следовательно, <tex>w(uv) \le w(ab)</tex>.<br />
}}<br />
<br />
Для доказательства минимальности <tex>K</tex> построим минимальное остовное дерево графа <tex>G</tex> используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз.<br />
На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано в утверждении выше, равен весу ребра из <tex>K</tex>, пересекающего этот разрез.<br />
Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>K</tex>, что и требовалось.<br />
<br />
}}<br />
== Уникальность остовного дерева ==<br />
{{Задача<br />
|definition=Поиск минимального остовного дерева и проверка его на уникальность.<br />
}}<br />
<h4>Алгоритм решения</h4><br />
Построим минимальное остовное дерево используя [[алгоритм Краскала]]. <br />
Рассмотрим рёбра вне остова в любом порядке. Очередное обозначим <tex>e = (u, v)</tex> . Рассмотрим максимальное ребро на пути <tex>u</tex> и <tex>v</tex> внутри остова:<br />
*Если его вес совпадает с весом ребра, то при добавлении ребра в остов, мы получим остов с циклом на котором несколько рёбер имеют одинаковый вес, значит мы можем удалить любое из них и остовное дерево будет всё ещё минимальным, это нарушает уникальность дерева. На этом алгоритм завершается и по критерию Тарьяна мы можем сказать, что в графе можно построить несколько остовных деревьев. <br />
*Если его вес больше ребра, то заменив ребро мы получим остов с большим весом, этот случай не влияет на уникальность. <br />
*Его вес не может быть меньше ребра из остова, иначе мы смогли бы построить минимальное остовное дерево с меньшим весом.<br />
После рассмотрения всех рёбер, если мы не нашли ребро вне остова, при добавлении которого создаётся цикл с максимальным ребром таким же как и на пути <tex>u</tex> и <tex>v</tex>, то в графе нету другого остовного дерева и наше дерево уникально.<br />
Искать максимальное ребро на пути <tex>u</tex> и <tex>v</tex> в дереве мы можем при помощи [[Heavy-light декомпозиция|heavy-light декомпозиции]].<br />
<h4>Асимптотика</h4><br />
Построение минимального остовного дерева работает за <tex>O(N \log N)</tex>, нахождение максимального ребра за <tex>O(\log N)</tex>, максимальное количество рёбер вне остова не больше <tex>N</tex>, каждое ребро проверяется за <tex>O(\log N)</tex>. Построение heavy-light декомпозиции работает за <tex>O(N)</tex>, остов мы построим один раз, heavy-light декомпозицию тоже один раз, каждое ребро мы не больше одного раза проверим на замену, сложность алгоритма <tex>O(N \log N)</tex>.<br />
<br />
== См.также ==<br />
* [[Остовные деревья: определения, лемма о безопасном ребре]]<br />
<br />
==Литература==<br />
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Остовные деревья ]]</div>176.59.13.228http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B9_%D0%A2%D0%B0%D1%80%D1%8C%D1%8F%D0%BD%D0%B0_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0&diff=58612Критерий Тарьяна минимальности остовного дерева2017-01-03T18:53:12Z<p>176.59.13.228: Дополнение(проверка уникальности минимального остова)</p>
<hr />
<div>{{Теорема<br />
|about=<br />
критерий Тарьяна минимальности остовного дерева<br />
|statement=<br />
Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево.<br />
|proof=<br />
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:<br />
если существует ребро, не максимальное на образовавшемся цикле, то мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.<br />
<br />
Теперь докажем, что дерево <tex>K</tex>, удовлетворяющее условию, минимально:<br />
<br />
{{Утверждение<br />
|statement=Для любого разреза <tex>\langle S, T \rangle</tex>, в котором ребро <tex>uv</tex> {{---}} единственное, пересекающее его в <tex>K</tex>, вес этого ребра минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез.<br />
<br />
|proof=Рассмотрим ребро <tex>ab \notin K</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>K</tex>.<br />
По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути.<br />
При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез.<br />
Но единственное такое ребро в остовном дереве {{---}} это <tex>uv</tex>.<br />
Следовательно, <tex>w(uv) \le w(ab)</tex>.<br />
}}<br />
<br />
Для доказательства минимальности <tex>K</tex> построим минимальное остовное дерево графа <tex>G</tex> используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз.<br />
На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано в утверждении выше, равен весу ребра из <tex>K</tex>, пересекающего этот разрез.<br />
Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>K</tex>, что и требовалось.<br />
<br />
{{Задача<br />
|definition=Проверка уникальности минимального остовного дерева<br />
}}<br />
Построим минимальное остовное дерево(MST) используя [[алгоритм Краскала]]. <br />
Рассмотрим рёбра <tex>ab</tex> вне остова, посмотрим на максимальное ребро на пути <tex>ab</tex> внутри остова:<br />
*Если его вес совпадает с весом ребра <tex>ab</tex>, то заменив ребро из остова ребром вне остова, мы получим остов с точно таким же весом, а значит остов не уникален. <br />
*Если его вес больше ребра из остова, значит заменив рёбра мы получим остов с большим весом, этот случай не влияет на уникальность. <br />
*Так же его вес не может быть меньше ребра из остова, иначе мы построили не минимальный остов в начале алгоритма.<br />
Искать максимальное ребро на пути <tex>ab</tex> в дереве мы можем при помощи алгоритма минимального общего предка(LCA), используя [[Метод двоичного подъема]].<br />
Построим дополнительный массив <tex>D</tex>, при помощи массива двоичных подъёмов. В <tex>D[i][j]</tex> храним номер ребра с максимальным весом на пути <tex>i-root</tex>, где <tex>i</tex> - номер вершины, <tex>j</tex> - степень подъёма(как в LCA). Когда нам нужно получить максимальное ребро на пути <tex>a-b</tex>, ищем максимальное ребро на пути <tex>a-root</tex>, <tex>b-root</tex> и выбираем максимальное из них.<br />
}}<br />
<h4>Асимптотика</h4><br />
Построение минимального остовного дерева работает за <tex>O(N \log N)</tex>, нахождение максимального ребра за <tex>O(\log N)</tex>, максимальное количество рёбер вне остова не больше <tex>N</tex>, каждое ребро проверяется за <tex>O(\log N)</tex>. Построение LCA и дополнительного массива работает за <tex>O(N \log N)</tex>, остов мы построим один раз, LCA тоже один раз, каждое ребро мы не больше одного раза проверим на замену, сложность алгоритма <tex>O(N \log N)</tex>.<br />
<br />
== См.также ==<br />
* [[Остовные деревья: определения, лемма о безопасном ребре]]<br />
<br />
==Литература==<br />
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Остовные деревья ]]</div>176.59.13.228