Изменения
Нет описания правки
# Пусть в графе $G$ есть вершина $s$, из которой достижимы все вершины. Обозначим как $\mu^*$ минимальный средний вес цикла в графе. Докажите, что $\mu^* = \min_v\max_k\frac{d_n(v)-d_k(v)}{n-k}$, где $d_i(v)$ - длина кратчайшего пути из $s$ до $v$, содержащего ровно $i$ ребер.
# Модифицируйте алгоритм Форда-Беллмана так, чтобы он находил в графе циклы минимального среднего веса за $O(VE)$ и $O(V^2)$ памяти.
# Доказать, что дерево $T$ является MST (здесь и далее MST - минимальное остовное дерево) тогда и только тогда, когда для любого ребра $uv \not\in T$ это ребро максимальное по весу на единственном цикле в графе $T \cup uv$. (Критерий Тарьяна)
# Используя критерий Тарьяна предложить алгоритм проверки того, что $T$ - MST, работающий за $O(E\times DSU)$
# [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8]. Доказать корректность работы алгоритма Борувки.
# Предложить реализацию алгоритма Борувки, работающую за $O(E \log V)$.
# Предложите реализацию алгоритма Борувки, работающую за $O(E \log^*V)$. (Указание - см. Freedman, Tarjan статью про фибоначчиевы кучи)
# Рассмотрим граф, вершины которого - остовные деревья $G$, а ребро между деревьями $T_1$ и $T_2$ существует, если $T_1$ получается из $T_2$ добавлением одного ребра и удалением другого. В нём рассмотрим подграф, состоящий только из $MST$. Доказать, что он связен.
# Рассмотрим граф. Упорядочим все его остовные деревья по возрастанию веса. Требуется найти вес второго в этом упорядочении дерева.
# Разработать алгоритм поиска всех рёбер, принадлежащих какому-нибудь MST за $O(VE)$.
# Петя пытается применить алгоритм Прима для ориентированного графа. Приведите пример графа, на котором Петя не сможет найти MST даже, если исходящее дерево из $s$ существует и Петя найдет какое-либо такое дерево.
# Коля пытается применить алгоритм Краскала для ориентированного графа. Приведите пример графа, на котором Коля не сможет найти MST, если исходящее дерево из $s$ существует и Коля найдет какое-либо такое дерево.
# Предложите реализацию алгоримта двух китайцев за $O(E \log E)$.
# Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST.
# Пусть $w(uv)$ - вес ребра, $c(uv)$ - стоимость ребра. Разработать алгоритм построения остовного дерева минимальной средней стоимости. (Отношение суммы стоимостей рёбер дерева к сумме весов рёбер дерева должно быть минимальным)
</wikitex>
