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

<wikitex>

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

Некоторые задания можно найти в книге Харари, Теория графов

1. Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
2. Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
3. Будем называть согласованным циклом в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл.
4. Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?
5. Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.
6. Харари 2.3
7. Харари 2.5
8. Харари 2.9
9. Харари 2.13
10. Харари 2.15
11. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
12. Харари 2.16
13. Харари 2.20
14. Харари 2.22
15. Харари 2.29
16. Харари 2.31
17. Харари 2.32
18. Харари 2.33
19. Харари 2.34 (а)
20. Харари 2.34 (б)
21. Харари 2.35
22. Харари 2.36
23. Харари 4.2
24. Харари 4.3
25. Харари 4.4
26. Харари 4.6
27. Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
28. Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
29. Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
30. При каких соотношениях $a$, $b$, $n$, $m$, $k$ существует граф с $a$ точками сочленения, $b$ мостами, $n$ вершинами, $m$ рёбрами, $k$ компонентами связности?
31. Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это рефлексивно-транзитивное замыкание $R$.
32. Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
33. Харари 3.2
34. Харари 3.3
35. Харари 3.4
36. Харари 3.5
37. Харари 3.6
38. Харари 3.7
39. Харари 3.9
40. Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых не более чем двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле.
41. Граф называется вершинно k-связным, если он остаётся связным после удаления любых не более чем (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле.
42. Пусть $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$.
43. Харари 5.2
44. Харари 5.5
45. Харари 5.6
46. Харари 5.7
47. В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла.
48. В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла.
49. В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла.
50. Харари 7.2
51. Харари 7.4
52. Харари 7.5
53. Харари 7.7
54. Харари 7.9
55. Харари 7.14
56. Харари 7.17
57. Харари 7.18
58. Харари 11.1
59. Харари 11.2
60. Харари 11.3
61. Харари 11.7
62. Харари 11.8
63. Харари 11.9
64. Харари 11.10
65. Харари 11.14
66. Харари 11.15
67. Харари 11.25
68. Посчитать хроматический многочлен цикла $C_n$
69. Посчитать хроматический многочлен колеса $C_n + K_1$.
70. Посчитать полного двудольного графа $K_{n,m}$.
71. Харари 12.2
72. Харари 12.3
73. Харари 12.4
74. Харари 12.5
75. Харари 12.6
76. Харари 12.12
77. Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
78. Доказать формулу Уитни: пусть $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$ рёбер.
79. Доказать теорему об отсутствии кратчайшего пути на базе алгоритма Форда-Беллмана. (от $s$ до $v$ нет кратчайшего пути тогда и только тогда, когда она достижима из $u$, такой что после выполнения алгоритма Форда-Беллмана найдется ребро $xu$, для которого $d[x] + w(xu) < d[u]$)
80. Разработать алгоритм на базе Форда-Беллмана, который ищет в графе отрицательный цикл.
81. Приведите пример графа с отрицательными рёбрами, но без отрицательных циклов, на котором алгоритм Дейкстры работает неверно.
82. Пусть веса рёбер не обязательно неотрицательны, но отрицательных циклов нет. Добавим в алгоритм Дейкстры следующее: если производится успешная релаксация по ребру $vx$ и $x \in U$, то вешина $x$ удаляется из $U$. Докажите, что, если этот алгоритм находит кратчайшие пути в графе.
83. Приведите пример графа, в котором алгоритм из предыдущего задания рабоатает экспоненциальное время.
84. Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе за O(VE).
85. Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм из предыдущего задания работает за $\Omega(VE)$.
86. Предложите граф, в котором алгоритм Дейкстры делает $\Omega(E)$ успешных релаксаций
87. Пусть в графе $G$ есть вершина $s$, из которой достижимы все вершины. Обозначим как $\mu^*$ минимальный средний вес цикла в графе. Докажите, что $\mu^* = \min_v\max_k\frac{d_n(v)-d_k(v)}{n-k}$, где $d_i(v)$ - длина кратчайшего пути из $s$ до $v$, содержащего ровно $i$ ребер.
88. Модифицируйте алгоритм Форда-Беллмана так, чтобы он находил в графе циклы минимального среднего веса за $O(VE)$ и $O(V^2)$ памяти.
89. Доказать, что дерево $T$ является MST (здесь и далее MST - минимальное остовное дерево) тогда и только тогда, когда для любого ребра $uv \not\in T$ это ребро максимальное по весу на единственном цикле в графе $T \cup uv$. (Критерий Тарьяна)
90. Используя критерий Тарьяна предложить алгоритм проверки того, что $T$ - MST, работающий за $O(E\times DSU)$
91. [1]. Доказать корректность работы алгоритма Борувки.
92. Предложить реализацию алгоритма Борувки, работающую за $O(E \log V)$.
93. Предложите реализацию алгоритма Борувки, работающую за $O(E \log^*V)$. (Указание - см. Freedman, Tarjan статью про фибоначчиевы кучи)
94. Рассмотрим граф, вершины которого - остовные деревья $G$, а ребро между деревьями $T_1$ и $T_2$ существует, если $T_1$ получается из $T_2$ добавлением одного ребра и удалением другого. В нём рассмотрим подграф, состоящий только из $MST$. Доказать, что он связен.
95. Рассмотрим граф. Упорядочим все его остовные деревья по возрастанию веса. Требуется найти вес второго в этом упорядочении дерева.
96. Разработать алгоритм поиска всех рёбер, принадлежащих какому-нибудь MST за $O(VE)$.
97. Петя пытается применить алгоритм Прима для ориентированного графа. Приведите пример графа, на котором Петя не сможет найти MST даже, если исходящее дерево из $s$ существует и Петя найдет какое-либо такое дерево.
98. Коля пытается применить алгоритм Краскала для ориентированного графа. Приведите пример графа, на котором Коля не сможет найти MST, если исходящее дерево из $s$ существует и Коля найдет какое-либо такое дерево.
99. Предложите реализацию алгоримта двух китайцев за $O(E \log E)$.
100. Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST.
101. Пусть $w(uv)$ - вес ребра, $c(uv)$ - стоимость ребра. Разработать алгоритм построения остовного дерева минимальной средней стоимости. (Отношение суммы стоимостей рёбер дерева к сумме весов рёбер дерева должно быть минимальным)
102. Сформулируйте и докажите аналогичную лемме о сумме лемму о разности потоков.
103. Вспомните граф, показанный на лекции, где пропускные способности трех средних ребер 1, $\varphi$ и $\varphi^2$. Предложите последовательность дополняющих путей в этом графе, при выборе которых максимальный поток никогда не будет найден.
104. Будем жадно выбирать для дополнения путь с максимальной остаточной пропускной способностью. Докажите, что при этом в сети с целочисленными пропускными способностями время работы алгоритма будет $O(poly(V, E) \log(C_{max}))$, где $C_{max}$ - максимальная пропускная способность ребра, а $poly$ - некоторый полином.
105. Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(VE)$ дополнений (сеть "грибок")
106. Докажите, что для любых $V$ и $E$ ($E = O(V^2)$, $E = \Omega(V)$) существует граф с $V$ вершинами и $E$ ребрами, в котором любая декомпозиция любого максимального потока содержит $\Omega(E)$ слагаемых, каждое из которых есть путь/цикл длины $\Omega(V)$.
107. Поток назовём циркуляцией, если его величина равна 0. Пусть в графе $G$ заданы две функции на ребрах: $L: E\to \mathbb{R}$ и $U: E\to \mathbb{R}$. Будем называть циркуляцию допустимой, если $L(uv) \le f(uv) \le R(uv)$. Требуется свести задачу поиска допустимой циркуляции в сети к задаче о максимальном потоке.
108. Сведите задачу о максимальном потоке с несколькими истоками и несколькими стоками к обычной задаче о максимальном потоке.
109. Можно ввести понятие пропускной способности вершины $c(u)$ как максимальной разрешенной суммы $\sum_{uv, f(uv) > 0}f(uv)$. Решите задачу о максимальном потоке для графа с пропускными способностями вершин.
110. Пусть $f_{max}$ - максимальный поток в сети, а $f_{blocking}$ - блокирующий поток. Доказать, что $|f_{blocking}| / |f_{max}|$ может быть сколь угодно мало.
111. Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
112. Предложите алгоритм проверки, что в графе единственный минимальный разрез
113. Петя в алгоритме Форда-Фалкерсона для поиска паросочетания в двудольном графе сделал ошибку: оставил рёбра между долями графа неориентированными. Построить пример, на котором алгоритм будет работать неправильно.
114. Доказать теорему Холла: что в двудольном графе $G$ существует полное паросочетание тогда и только тогда, когда для любого множества вершин левой доли $A \subset X$ выполнено $|N(A)| \ge |A|$. ($N(A)$ - множество соседей вершин из $A$)
115. Докажите, что в регулярном двудольном графе существует полное паросочетание.
116. Дефектом множества вершин левой доли в графе называется $def(A) = |N(A)| - |A|$. Найти в двудольном графе множество с минимальным дефектом.
117. Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом вершинно-непересекающихся путей. Сведите эту задачу к задаче о максимальном паросочетании.
118. Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом реберно-непересекающихся путей.
119. Докажите, что если в графе единственное полное паросочетание, то в нем есть мост
120. Предложите алгоритм проверки, что в двудольном графе четное число полных паросочетаний
121. Предложите алгоритм проверки по двудольному графу и заданному полному паросочетанию, является ли оно единственным в этом графе (за $O(E)$).
122. Предложите алгоритм для решения следующей задачи за $O(E)$. Дан двудольный граф и полное паросочетание в нем. Требуется выяснить для каждого ребра, лежит ли оно на некотором полном паросочетании.
123. Задача об устойчивом паросочетании. Задан двудольный граф с равным числом вершин в долях. Для каждой вершины каждой доли известен порядок предпочтения вершин другой доли (каждая вершина знает, какая вершина другой доли ей нравится больше всего, какая вершина на втором месте, и так далее). Паросочетание называется устойчивым, если никакие две вершины не могут обменяться парами, чтобы для каждой из них новый партнер стал более предпочтительным. Требуется построить устойчивое полное паросочетание за $O(VE)$.
124. Пусть $G$ - регулярный двудольный граф степени $k$. Докажите, что ребра $G$ можно разбить на $k$ полных паросочетаний.
125. Пусть $G$ - регулярный граф степени $k$, $U \subset V$, $U$ содержит нечетное число вершин и $m$ - число ребер, которые соединяют вершины $U$ с вершинами $V \setminus U$. Тогда $m$ четно тогда и только тогда, когда $k$ четно.
126. Докажите, что в двусвязном кубическом графе есть полное паросочетание.
127. Докажите, что если в кубическом графе не более двух мостов, то в нем есть полное паросочетание.
128. Приведите пример кубического графа, в котором нет полного паросочетания.
129. Предложите алгоритм разбиения регулярного двудольного графа степени $k$ на $k$ совершенных паросочетаний за время $O(VE)$.
130. Докажите, что ребра двудольного графа можно раскрасить в $k$ цветов, где $k$ - максимальная степень вершины, причем никакие два ребра, инцидентные одной вершине, не будут иметь одинаковый цвет.
131. Пусть максимальное паросочетание в графе $G$ имеет размер $k$. Каким может быть размер максимального по включению паросочетания в $G$?
132. Докажите, что любое дерево имеет не более одного полного паросочетания. Верно ли это для максимальных, но не полных паросочетаний?
133. Докажите, что если в графе четное число вершин и любая вершина имеет степень хотя бы $n / 2$, то в таком графе есть полное паросочетание. Можно ли усилить это утверждение?
134. Рассмотрим в двудольном графе с долями $X$ и $Y$ множества $S\subset X$ и $T \subset Y$. Пусть существуют паросочетания $M_S$ и $M_T$, которые покрывают $S$ и $T$, соответственно. Докажите, что существует паросочетание, которое покрывает $S\cup T$.
135. Докажите, что граф с $2n$ вершинами и степенью любой вершины не больше $k$ имеет не более $k^n$ различных полных паросочетаний.
136. Дайте оценку, аналогичную оценке из предыдущего задания, для двудольного графа с долями, содержащими по $n$ вершин.
137. Завершите доказательство теоремы о сжатии соцветий.
138. Будем называть множество ребер набором 1-2-путей, если любая компонента связности в этом множестве является содержит не более двух ребер. Предложите алгоритм построения набора 1-2-путей в двудольном графе, покрывающего все вершины.
139. В регулярном графе $G$ степень любой вершины $k$ и $\lambda(G) \ge k - 1$. Докажите, что в $G$ есть полное паросочетание.
140. Докажите, что ребра кубического графа можно раскрасить в разные цвета так, что для каждого цвета существует ровно три ребра этого цвета, причем они представляют собой простой путь.
141. Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число операций relabel с каждой вершиной не превышает $3V$.
142. Пусть $f$ - поток, а $f'$ - псевдопоток (выполнены все аксиомы, кроме сохранения потока). Пусть в вершине $u$ есть положительный избыток $f'$. Докажите, что в $G_f$ есть путь из $u$ до некоторой вершины, в которой есть положительный недостаток $f'$ по ненасыщенным ребрам.
143. Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число насыщающих операций push есть $O(VE)$.
144. Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число ненасыщающих операций push есть $O(V^2E)$.
145. Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число ненасыщающих операций push есть $O(V^2E)$.
146. Пусть $f^*$ - поток минимальной стоимости. Пусть поток $f$ является $\varepsilon$-оптимальным, причем $\varepsilon(f)=\varepsilon$. Пусть $\varepsilon' < \varepsilon/V$. Докажите, что если $f'$ является $\varepsilon'$-оптимальным потоком, то существует ребро, поток $f'$ по которому совпадает с потоком $f^*$, а поток $f$ - нет.
147. Докажите, что если $\varepsilon(f) = \varepsilon$ и $f'$ получен из $f$ дополнением по циклу минимальной средней стоимости, то $\varepsilon(f')\le (1-1/V)\varepsilon$.

</wikitex>