21
правка
Изменения
Нет описания правки
# Предложите аналогичный заданию 95 алгоритм поиска раскраски графа в два цвета.
# Почему алгоритм из предыдущего задания не работает для поиска раскраски графа в три цвета?
# Обозначим как $m_k(G)$ количество паросочетаний размера $k$ в двудольном графе $G$, каждая доля которого содержит по $n$ вершин. Пусть граф содержит больше $k$ ребер. Докажите, что существует ребро $uv$, такое что $m_k(G)/m_k(G\setminus uv) \le n$.
# Пусть вероятностный алгоритм $U_k$ получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$, причем все паросочетания равновероятны. Покажите, как с использованием $U_k$ получить $\varepsilon$-$\delta$-FRPAS для доли паросочетаний, содержащих заданное ребро $uv$ в графе $G$.
# Покажите, как с использованием $U_k$ из предедыдущего задания получить $\varepsilon$-$\delta$-FRPAS для числа $m_k(G)$.
# Будем называть полиномиальный вероятностный алгоритм $U_k$ равномерным с точностью до $\rho$ генератором, если он получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$, причем для любого паросочетания $M$ $|P(U_k(G)=M) - 1/m_k(G)| \le \rho/m_k(G)$. Пусть $\rho \le 1/n^b$ для некоторого $b$. Подберите константу $b$, чтобы можно было решить задание 84, используя равномерный с точностью до $\rho$ генератор.
# Подберите константу $b$, чтобы можно было решить задание 85, используя равномерный с точностью до $\rho$ генератор.
# Пусть полиномиальный вероятностный алгоритм $\hat U_k$ получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$ или $k-1$, причем все паросочетания равновероятны. Пусть $r = m_k(G)/m_{k-1}(G)$ удовлетворяет условию $1/n^2 \le r \le n^2$. Докажите, что с помощью $\hat U_k$ можно получить $\varepsilon$-$\delta$-FRPAS для $m_k(G)$.
# Подберите константу $b$, чтобы можно было решить задание 88, используя равномерный с точностью до $\rho \le 1/n^b$ генератор.
# Докажите, что если степень любой вершины в графе не меньше $n/2$, то выполнено условие $1/n^2 \le r \le n^2$ для задания 88.
# Соедините предыдущие задания, чтобы получить из существования равномерного с точностью до $\rho \le 1/n^b$ генератора $\hat U_k$ для любого $k$ $\varepsilon$-$\delta$-FPRAS для числа совершенных паросочетаний в двудольном графе, где степени всех вершин не меньше $n/2$.
# Рассмотрим $\varepsilon$-$\delta$-FPRAS $A$ для числа паросочетаний в двудольном графе. Используя $A$, постройте полиномиальный вероятностный алгоритм, который является равномерным генератором с точностью до $\rho = o(1)$.
# Пусть существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в двудольном графе, степень каждой вершины которого равна хотя бы $\beta n$, где $0 < \beta < 1$. Докажите, что существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в произвольном двудольном графе.
# Рассмотрим алгоритм приближения числа $\pi$. Будем генерировать точки с равномерным распределением в квадрате $1 \times 1$ и считать долю попавших в круг диаметром 1, вписанный в этот квадрат. Оцените число итераций, необходимое, чтобы приблизить $\pi$ с точностью до $\varepsilon$.
# Пусть матрица переходов эргодической марковской цепи является дважды стохастической (сумма элементов каждого столбца также равна 1). Докажите, что стационарное распределение $(1/n, 1/n, \ldots, 1/n)$.
# Пусть матрицы $A$ и $B$ имеют один и тот же собственный вектор $x$ для собственных чисел $\lambda$ и $\mu$, соответственно. Докажите, что $x$ является собственным вектором для $A+B$. Для какого собственного числа?
