Изменения

Перейти к: навигация, поиск

Список заданий по АСД 2к 2015 осень

3093 байта добавлено, 11:49, 20 ноября 2015
Нет описания правки
# Сведите задачу о максимальном потоке с несколькими истоками и несколькими стоками к обычной задаче о максимальном потоке.
# Можно ввести понятие пропускной способности вершины $c(u)$ как максимальной разрешенной суммы $\sum_{uv}f(uv)$. Решите задачу о максимальном потоке для графа с пропускными способностями вершин.
# Доказать, что дерево $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.
Анонимный участник

Навигация