Изменения
Нет описания правки
# Задан несильносвязный турнир. Турнир {{---}} ориентированный граф, в котором между любыми двумя вершинами есть ровно одно ребро, либо в одну сторону, либо в другую. Найдите число способов развернуть одно ребро так, чтобы все вершины стали сильносвязными за $O(V^2)$.
# Приведите пример графа с отрицательными рёбрами, но без отрицательных циклов, на котором алгоритм Дейкстры работает неверно.
# Есть взвешенный граф, где веса ребер, исходящих из одной вершины, одинаковы. Докажите, что как модифицировать алгоритм Дейкстры, реализованный с помощью двоичной кучи, будет работать за $O(V\log{V} + E)$чтобы для каждой вершины происходила ровно одна релаксация.
# Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе за $O(VE)$.
# Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм из предыдущего задания работает за $\Omega(VE)$.
# Предложите алгоритм поиска всех ребер, которые лежат во всех 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>
