Изменения
Нет описания правки
# Задан ориентированный граф, у каждой вершины исходящая степень равна 1. У каждого ребра есть вес. Вы забыли про ориентацию ребер, найдите паросочетание максимального веса за $O(E + V)$.
# Предложите алгоритм, который добавляет в ацикличный ориентированный граф ровно одно ребро, чтобы он остался ацикличным, так, чтобы максимальный по длине путь был как можно длиннее за $O(V^2 + E)$.
# Задан ориентированный граф. В вершинах записаны числа от 1 до $|V|$, все различные. Профилем вершины назовем следующую последовательность: возьмем все вершины достижимые из нее, все числа записанные на этих вершинах и упорядочим. Отсортируйте вершины по профилю лексикографически за $O(E + V)$.
# Задан ацикличный ориентированный граф. Удалите в нем одно ребро, чтобы число простых путей в графе стало как можно меньше за $O(E + V)$.
# Задан ориентированный граф, в каждой вершине записано число. Для каждой вершины $v$ найдите $f(v)$ {{---}} вершину с максимальным числом, которая достижима из $v$, за $O(E + V)$.
# Задан неориентированный граф. Покрасьте граф в два цвета, чтобы число вершин первого цвета было равно числу вершин второго цвета за $O(V^2+E)$.# Задан неориентированный граф. На каждом ребре записан бит 0 или 1. В каждой вершине расположена кнопка, нажав на которую, меняют значения все биты на ребрах, инцидентных данной вершине. Вычислите, за какое минимальное число нажатий на кнопку биты на всех ребрах окажутся равны нулю, за $O(E + V)$.# Задан ориентированный граф улиц в городе. Нужно поставить полицейские станции в вершинах. Всего нужно поставить ровно $k$ станций так, чтобы из каждой вершины была достижима хотя бы одна станция и каждая вершина была достижима из хотя бы одной станции. Выведите число способов поставить $k$ станций в $k$ различных вершин за $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>
