Список заданий по АСД

2014-12-14T21:15:44Z

46.165.196.71:

<wikitex>
= Дискретная математика, алгоритмы и структуры данных, 3 семестр =

Некоторые задания можно найти в книге [http://www.ozon.ru/context/detail/id/4452506/ Харари, Теория графов]

# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
# Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
# Будем называть ''согласованным циклом'' в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл.
# Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?
# Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.
# Харари 2.3
# Харари 2.5
# Харари 2.9
# Харари 2.13
# Харари 2.15
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
# Харари 2.16
# Харари 2.20
# Харари 2.22
# Харари 2.29
# Харари 2.31
# Харари 2.32
# Харари 2.33
# Харари 2.34 (а)
# Харари 2.34 (б)
# Харари 2.35
# Харари 2.36
# Харари 4.2
# Харари 4.3
# Харари 4.4
# Харари 4.6
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
# Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
# При каких соотношениях $a$, $b$, $n$, $m$, $k$ существует граф с $a$ точками сочленения, $b$ мостами, $n$ вершинами, $m$ рёбрами, $k$ компонентами связности?
# Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это рефлексивно-транзитивное замыкание $R$.
# Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
# Харари 3.2
# Харари 3.3
# Харари 3.4
# Харари 3.5
# Харари 3.6
# Харари 3.7
# Харари 3.9
# Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых не более чем двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле.
# Граф называется вершинно k-связным, если он остаётся связным после удаления любых не более чем (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле.
# Пусть $G$ - связный граф. Обозначим как $\kappa(G)$ - минимальное число вершин, которое необходимо удалить, чтобы граф потерял связность. (для полного графа это число равно n - 1), $\lambda(G)$ - минимальное число рёбер, которое необходимо удалить, чтобы граф потерял связность, $\delta(G)$ - минимальную степень в вершины в графе $G$. Докажите, что для любых $a$, $b$, $c$, таких что $1 \le a \le b \le c$, существует граф $G$, такой что $\kappa(G) = a$, $\lambda(G) = b$, $\delta(G) = c$.
# Харари 5.2
# Харари 5.5
# Харари 5.6
# Харари 5.7
# В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла.
# В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла.
# В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла.
# Харари 7.2
# Харари 7.4
# Харари 7.5
# Харари 7.7
# Харари 7.9
# Харари 7.14
# Харари 7.17
# Харари 7.18
# Харари 11.1
# Харари 11.2
# Харари 11.3
# Харари 11.7
# Харари 11.8
# Харари 11.9
# Харари 11.10
# Харари 11.14
# Харари 11.15
# Харари 11.25
# Посчитать хроматический многочлен цикла $C_n$
# Посчитать хроматический многочлен колеса $C_n + K_1$.
# Посчитать полного двудольного графа $K_{n,m}$.
# Харари 12.2
# Харари 12.3
# Харари 12.4
# Харари 12.5
# Харари 12.6
# Харари 12.12
# Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
# Доказать формулу Уитни: пусть $G$ - обыкновенный $(n, m)$ - граф. Тогда коэффициент при $x^i$, где $1\le i\le n$ в хроматическом многочлене $P_G(x)$ равен $\sum \limits_{j=0}^{m}{(-1)^jN(i, j)}$, где $N(i, j)$ - число остовных подграфов графа $G$, имеющих $i$ компонент связности и $j$ рёбер.
# Доказать теорему об отсутствии кратчайшего пути на базе алгоритма Форда-Беллмана. (от $s$ до $v$ нет кратчайшего пути тогда и только тогда, когда она достижима из $u$, такой что после выполнения алгоритма Форда-Беллмана найдется ребро $xu$, для которого $d[x] + w(xu) < d[u]$)
# Разработать алгоритм на базе Форда-Беллмана, который ищет в графе отрицательный цикл.
# Приведите пример графа с отрицательными рёбрами, но без отрицательных циклов, на котором алгоритм Дейкстры работает неверно.
# Пусть веса рёбер не обязательно неотрицательны, но отрицательных циклов нет. Добавим в алгоритм Дейкстры следующее: если производится успешная релаксация по ребру $vx$ и $x \in U$, то вешина $x$ удаляется из $U$. Докажите, что, если этот алгоритм находит кратчайшие пути в графе.
# Приведите пример графа, в котором алгоритм из предыдущего задания рабоатает экспоненциальное время.
# Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе за O(VE).
# Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм из предыдущего задания работает за $\Omega(VE)$.
# Предложите граф, в котором алгоритм Дейкстры делает $\Omega(E)$ успешных релаксаций
# Пусть в графе $G$ есть вершина $s$, из которой достижимы все вершины. Обозначим как $\mu^*$ минимальный средний вес цикла в графе. Докажите, что $\mu^* = \min_v\max_k\frac{d_n(v)-d_k(v)}{n-k}$, где $d_i(v)$ - длина кратчайшего пути из $s$ до $v$, содержащего ровно $i$ ребер.
# Модифицируйте алгоритм Форда-Беллмана так, чтобы он находил в графе циклы минимального среднего веса за $O(VE)$ и $O(V^2)$ памяти.
# Доказать, что дерево $T$ является MST (здесь и далее MST - минимальное остовное дерево) тогда и только тогда, когда для любого ребра $uv \not\in T$ это ребро максимальное по весу на единственном цикле в графе $T \cup uv$. (Критерий Тарьяна)
# Используя критерий Тарьяна предложить алгоритм проверки того, что $T$ - MST, работающий за $O(E\times DSU)$
# [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8]. Доказать корректность работы алгоритма Борувки.
# Предложить реализацию алгоритма Борувки, работающую за $O(E \log V)$.
# Предложите реализацию алгоритма Борувки, работающую за $O(E \log^*V)$. (Указание - см. Freedman, Tarjan статью про фибоначчиевы кучи)
# Рассмотрим граф, вершины которого - остовные деревья $G$, а ребро между деревьями $T_1$ и $T_2$ существует, если $T_1$ получается из $T_2$ добавлением одного ребра и удалением другого. В нём рассмотрим подграф, состоящий только из $MST$. Доказать, что он связен.
# Рассмотрим граф. Упорядочим все его остовные деревья по возрастанию веса. Требуется найти вес второго в этом упорядочении дерева.
# Разработать алгоритм поиска всех рёбер, принадлежащих какому-нибудь MST за $O(VE)$.
# Петя пытается применить алгоритм Прима для ориентированного графа. Приведите пример графа, на котором Петя не сможет найти MST даже, если исходящее дерево из $s$ существует и Петя найдет какое-либо такое дерево.
# Коля пытается применить алгоритм Краскала для ориентированного графа. Приведите пример графа, на котором Коля не сможет найти MST, если исходящее дерево из $s$ существует и Коля найдет какое-либо такое дерево.
# Предложите реализацию алгоримта двух китайцев за $O(E \log E)$.
# Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST.
# Пусть $w(uv)$ - вес ребра, $c(uv)$ - стоимость ребра. Разработать алгоритм построения остовного дерева минимальной средней стоимости. (Отношение суммы стоимостей рёбер дерева к сумме весов рёбер дерева должно быть минимальным)
# Сформулируйте и докажите аналогичную лемме о сумме лемму о разности потоков.
# Вспомните граф, показанный на лекции, где пропускные способности трех средних ребер 1, $\varphi$ и $\varphi^2$. Предложите последовательность дополняющих путей в этом графе, при выборе которых максимальный поток никогда не будет найден.
# Будем жадно выбирать для дополнения путь с максимальной остаточной пропускной способностью. Докажите, что при этом в сети с целочисленными пропускными способностями время работы алгоритма будет $O(poly(V, E) \log(C_{max}))$, где $C_{max}$ - максимальная пропускная способность ребра, а $poly$ - некоторый полином.
# Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(VE)$ дополнений (сеть "грибок")
# Докажите, что для любых $V$ и $E$ ($E = O(V^2)$, $E = \Omega(V)$) существует граф с $V$ вершинами и $E$ ребрами, в котором любая декомпозиция любого максимального потока содержит $\Omega(E)$ слагаемых, каждое из которых есть путь/цикл длины $\Omega(V)$.
# Поток назовём циркуляцией, если его величина равна 0. Пусть в графе $G$ заданы две функции на ребрах: $L: E\to \mathbb{R}$ и $U: E\to \mathbb{R}$. Будем называть циркуляцию допустимой, если $L(uv) \le f(uv) \le R(uv)$. Требуется свести задачу поиска допустимой циркуляции в сети к задаче о максимальном потоке.
# Сведите задачу о максимальном потоке с несколькими истоками и несколькими стоками к обычной задаче о максимальном потоке.
# Можно ввести понятие пропускной способности вершины $c(u)$ как максимальной разрешенной суммы $\sum_{uv, f(uv) > 0}f(uv)$. Решите задачу о максимальном потоке для графа с пропускными способностями вершин.
# Пусть $f_{max}$ - максимальный поток в сети, а $f_{blocking}$ - блокирующий поток. Доказать, что $|f_{blocking}| / |f_{max}|$ может быть сколь угодно мало.
# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
# Предложите алгоритм проверки, что в графе единственный минимальный разрез
# Петя в алгоритме Форда-Фалкерсона для поиска паросочетания в двудольном графе сделал ошибку: оставил рёбра между долями графа неориентированными. Построить пример, на котором алгоритм будет работать неправильно.
# Доказать теорему Холла: что в двудольном графе $G$ существует полное паросочетание тогда и только тогда, когда для любого множества вершин левой доли $A \subset X$ выполнено $|N(A)| \ge |A|$. ($N(A)$ - множество соседей вершин из $A$)
# Докажите, что в регулярном двудольном графе существует полное паросочетание.
# Дефектом множества вершин левой доли в графе называется $def(A) = |N(A)| - |A|$. Найти в двудольном графе множество с минимальным дефектом.
# Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом вершинно-непересекающихся путей. Сведите эту задачу к задаче о максимальном паросочетании.
# Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом реберно-непересекающихся путей.
# Докажите, что если в графе единственное полное паросочетание, то в нем есть мост
# Предложите алгоритм проверки, что в двудольном графе четное число полных паросочетаний
# Предложите алгоритм проверки по двудольному графу и заданному полному паросочетанию, является ли оно единственным в этом графе (за $O(E)$).
# Предложите алгоритм для решения следующей задачи за $O(E)$. Дан двудольный граф и полное паросочетание в нем. Требуется выяснить для каждого ребра, лежит ли оно на некотором полном паросочетании.
# Задача об устойчивом паросочетании. Задан двудольный граф с равным числом вершин в долях. Для каждой вершины каждой доли известен порядок предпочтения вершин другой доли (каждая вершина знает, какая вершина другой доли ей нравится больше всего, какая вершина на втором месте, и так далее). Паросочетание называется устойчивым, если никакие две вершины не могут обменяться парами, чтобы для каждой из них новый партнер стал более предпочтительным. Требуется построить устойчивое полное паросочетание за $O(VE)$.
# Пусть $G$ - регулярный двудольный граф степени $k$. Докажите, что ребра $G$ можно разбить на $k$ полных паросочетаний.
# Пусть $G$ - регулярный граф степени $k$, $U \subset V$, $U$ содержит нечетное число вершин и $m$ - число ребер, которые соединяют вершины $U$ с вершинами $V \setminus U$. Тогда $m$ четно тогда и только тогда, когда $k$ четно.
# Докажите, что в двусвязном кубическом графе есть полное паросочетание.
# Докажите, что если в кубическом графе не более двух мостов, то в нем есть полное паросочетание.
# Приведите пример кубического графа, в котором нет полного паросочетания.
# Предложите алгоритм разбиения регулярного двудольного графа степени $k$ на $k$ совершенных паросочетаний за время $O(VE)$.
# Докажите, что ребра двудольного графа можно раскрасить в $k$ цветов, где $k$ - максимальная степень вершины, причем никакие два ребра, инцидентные одной вершине, не будут иметь одинаковый цвет.
# Пусть максимальное паросочетание в графе $G$ имеет размер $k$. Каким может быть размер максимального по включению паросочетания в $G$?
# Докажите, что любое дерево имеет не более одного полного паросочетания. Верно ли это для максимальных, но не полных паросочетаний?
# Докажите, что если в графе четное число вершин и любая вершина имеет степень хотя бы $n / 2$, то в таком графе есть полное паросочетание. Можно ли усилить это утверждение?
# Рассмотрим в двудольном графе с долями $X$ и $Y$ множества $S\subset X$ и $T \subset Y$. Пусть существуют паросочетания $M_S$ и $M_T$, которые покрывают $S$ и $T$, соответственно. Докажите, что существует паросочетание, которое покрывает $S\cup T$.
# Докажите, что граф с $2n$ вершинами и степенью любой вершины не больше $k$ имеет не более $k^n$ различных полных паросочетаний.
# Дайте оценку, аналогичную оценке из предыдущего задания, для двудольного графа с долями, содержащими по $n$ вершин.
# Завершите доказательство теоремы о сжатии соцветий.
# Будем называть множество ребер набором 1-2-путей, если любая компонента связности в этом множестве является содержит не более двух ребер. Предложите алгоритм построения набора 1-2-путей в двудольном графе, покрывающего все вершины.
# В регулярном графе $G$ степень любой вершины $k$ и $\lambda(G) \ge k - 1$. Докажите, что в $G$ есть полное паросочетание.
# Докажите, что ребра кубического графа можно раскрасить в разные цвета так, что для каждого цвета существует ровно три ребра этого цвета, причем они представляют собой простой путь.
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число операций relabel с каждой вершиной не превышает $3V$.
# Пусть $f$ - поток, а $f'$ - псевдопоток (выполнены все аксиомы, кроме сохранения потока). Пусть в вершине $u$ есть положительный избыток $f'$. Докажите, что в $G_f$ есть путь из $u$ до некоторой вершины, в которой есть положительный недостаток $f'$ по ненасыщенным ребрам.
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число насыщающих операций push есть $O(VE)$.
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число ненасыщающих операций push есть $O(V^2E)$.
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число ненасыщающих операций push есть $O(V^2E)$.
# Пусть $f^*$ - поток минимальной стоимости. Пусть поток $f$ является $\varepsilon$-оптимальным, причем $\varepsilon(f)=\varepsilon$. Пусть $\varepsilon' < \varepsilon/V$. Докажите, что если $f'$ является $\varepsilon'$-оптимальным потоком, то существует ребро, поток $f'$ по которому совпадает с потоком $f^*$, а поток $f$ - нет.
# Докажите, что если $\varepsilon(f) = \varepsilon$ и $f'$ получен из $f$ дополнением по циклу минимальной средней стоимости, то $\varepsilon(f')\le (1-1/V)\varepsilon$.
</wikitex>

Викиконспекты - Вклад участника [ru]

Список заданий по АСД