Изменения
Нет описания правки
# Задан неориентированный граф, степень каждой вершины не больше двух. Найдите минимальное вершинное покрытие в графе за $O(E + V)$.
# Задан несильносвязный турнир. Турнир {{---}} ориентированный граф, в котором между любыми двумя вершинами есть ровно одно ребро, либо в одну сторону, либо в другую. Найдите число способов развернуть одно ребро так, чтобы все вершины стали сильносвязными за $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)$.# Предложите граф, в котором алгоритм Дейкстры делает $\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})$.#
</wikitex>
