1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Задан ориентированный граф, у каждой вершины исходящая степень равна 1. У каждого ребра есть вес. Вы забыли про ориентацию ребер, найдите паросочетание максимального веса за $O(E + V)$.
# Предложите алгоритм, который добавляет в ацикличный ориентированный граф ровно одно ребро, чтобы он остался ацикличным, так, чтобы максимальный по длине путь был как можно длиннее за $O(V^2 + E)$.
# Задан ориентированный граф. В вершинах записаны числа от 1 до $|V|$, все различные. Профилем вершины назовем следующую последовательность: возьмем все вершины достижимые из нее, все числа записанные на этих вершинах и упорядочим. Отсортируйте вершины по профилю лексикографически за $O(E + V)$.
# Задан ацикличный ориентированный граф. Удалите в нем одно ребро, чтобы число простых путей в графе стало как можно меньше за $O(E + V)$.
# Задан ориентированный граф, в каждой вершине записано число. Для каждой вершины $v$ найдите $f(v)$ {{---}} вершину с максимальным числом, которая достижима из $v$, за $O(E + V)$.
# Задан неориентированный граф, степень каждой вершины не больше двух. Найдите минимальное вершинное покрытие в графе за $O(E + V)$.
# Задан несильносвязный турнир. Турнир {{---}} ориентированный граф, в котором между любыми двумя вершинами есть ровно одно ребро, либо в одну сторону, либо в другую. Найдите число способов развернуть одно ребро так, чтобы все вершины стали сильносвязными за $O(V^2)$.
# Приведите пример графа с отрицательными рёбрами, но без отрицательных циклов, на котором алгоритм Дейкстры работает неверно.# Есть взвешенный граф, где веса ребер, исходящих из одной вершины, одинаковы. Докажите, как модифицировать алгоритм Дейкстры, чтобы для каждой вершины происходила ровно одна релаксация.# Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе за $O(VE)$.# Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм из предыдущего задания работает за $\Omega(VE)$.# Предложите граф, в котором алгоритм Дейкстры делает $\Omega(E)$ успешных релаксаций# Предложите алгоритм поиска цикла "почти" минимального среднего веса (отношение суммы весов ребер и числа ребер) за $O(VE \log{\frac{1}{\epsilon}})$, средний вес цикла должен отличаться от оптимального не более чем на $\epsilon$.# Доказать, что дерево $T$ является MST (здесь и далее MST - минимальное остовное дерево) тогда и только тогда, когда для любого ребра $uv \not\in T$ это ребро максимальное по весу на единственном цикле в графе $T \cup uv$. (Критерий Тарьяна)# Рассмотрим все остовные деревья графа, отсортируем их по весу. Предложите алгоритм, который выдаст вес второго MST в этом списке за $O(E \log{V})$.# Рассмотрим граф, вершины которого {{---}} остовные деревья $G$, а ребро между деревьями $T_1$ и $T_2$ существует, если $T_1$ получается из $T_2$ добавлением одного ребра и удалением другого. В нём рассмотрим подграф, состоящий только из $MST$. Доказать, что он связен.# Предложите алгоритм поиска всех ребер, которые лежат хотя бы в одном MST за $O(E \log{V})$.# Предложите алгоритм поиска всех ребер, которые лежат во всех MST за $O(E \log{V})$.# Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе с отрицательными ребрами, но без отрицательных циклов, за $O(VE)$.# Вы запустили алгоритм Форда-Беллмана. Насколько большими и насколько маленькими бывают значения чисел в массиве расстояний, если у вас $V$ вершин, $E$ ребер и вес каждого ребра по модулю не превосходит $C$.# Вы запустили алгоритм Флойда. Насколько большими и насколько маленькими бывают значения чисел в массиве расстояний, если у вас $V$ вершин, $E$ ребер и вес каждого ребра по модулю не превосходит $C$.# Модифицированная задача о рюкзаке. У вас есть $n$ номиналов монеток. Каждая монета с целой ценностью не более $c$. Каждого из $n$ номиналов у вас имеется неограниченное число монеток. Ответьте на много запросов: можете ли вы набрать сумму $W$, каждый запрос за $O(1)$, с предпосчетом за $O(nc\log{c})$# Задан неориентированный граф, все веса положительные целые числа не превосходящие $c$. Вам нужно узнать, существует ли путь из вершины $s$ в вершину $t$, с весом равным $W$ за $O(Ec \log{c})$.
</wikitex>
