206
правок
Изменения
Нет описания правки
# Нижняя оценка на сумму длин путей. Докажите, что можно построить граф, в котором $\Omega(n^2)$ пар вершин, расстояние между которыми $\Omega(n)$.
# Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно?
# Петя хочет упростить алгоритм Каргера-Штайна. Он запускает алгоритм Каргера (стягивание по случайному ребру), пока количество вершин не станет равно $t$, а затем запускает алгоритм за $t^3$ поиска минимального глобального разреза. Затем он повторяет алгоритм, пока вероятность успеха не составит хотя бы $1/2$. Какое значение $t$ необходимо выбрать, чтобы минимизировать время работы получившегося алгоритма? Какое будет время работы?
# Докажите, что если в полном двоичном дереве высоты $h$ каждое ребро удаляется с вероятностью $1/2$, то путь от корня до листа сохраняется с вероятностью $\Theta(1/h)$.
# Обобщите предыдущее задание, если ребро удаляется с вероятностью $p$.
# С учетом предыдущего задания модифицируйте алгоритм Каргера-Штайна, чтобы разветвляться когда накопленная вероятность ошибки достигнет $p$. Найдите зависимость времени работы от $p$, какое значение $p$ оптимально выбрать?
# Назовем разрез $\alpha$-оптимальным, если его размер не больше $\alpha C_{min}$, где $C_{min}$ - минимальный разрез. Оцените вероятность, что один запуск алгоритма Каргера (без разветвлений) найдет $\alpha$-оптимальный разрез (в зависимости от $\alpha$).
# Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов.
# Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов.
