Список заданий по АСД 2к 2015 осень

<wikitex>

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. Рассмотрим неориентированный граф $G$. Запустим dfs, затем ориентируем рёбра дерева dfs $T$ от корня, а остальные - к корню. Доказать, что компоненты сильной связности в получившемся графе равны компонентам рёберной двусвязности в исходном графе
44. Разработать алгоритм поиска компонент рёберной двусвязности, используя ровно один запуск dfs.
45. Разработать алгоритм поиска компонент вершинной двусвязности, используя ровно один запуск dfs.
46. Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2\not\in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
47. Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2 \in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
48. В первом издании Кормена была ошибка. Там было сказано, что вершина v есть точка сочленения тогда и только тогда, когда (v - корень И у v ≥ 2 сына) ИЛИ (v - не корень И up[v] ≥ enter[v]). Приведите контрпример.
49. Приведите пример графа с отрицательными рёбрами, на котором алгоритм Дейкстры работает неверно.
50. Пусть веса рёбер не обязательно неотрицательны, но отрицательных циклов нет. Добавим в алгоритм Дейкстры следующее: если производится успешная релаксация по ребру $vx$ и $x \in U$, то вешина $x$ удаляется из $U$. Докажите, что, если этот алгоритм находит кратчайшие пути в графе.
51. Приведите пример графа, в котором алгоритм из предыдущего задания рабоатает экспоненциальное время.
52. Предложите граф, в котором алгоритм Дейкстры делает $\Omega(E)$ успешных релаксаций
53. Доказать теорему об отсутствии кратчайшего пути на базе алгоритма Форда-Беллмана. (от $s$ до $v$ нет кратчайшего пути тогда и только тогда, когда она достижима из $u$, такой что после выполнения алгоритма Форда-Беллмана найдется ребро $xu$, для которого $d[x] + w(xu) < d[u]$)
54. Разработать алгоритм на базе Форда-Беллмана, который ищет в графе отрицательный цикл.
55. Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм Форда-Беллмана с очередью работает за $\Omega(VE)$.
56. Пусть в графе $G$ есть вершина $s$, из которой достижимы все вершины. Обозначим как $\mu^*$ минимальный средний вес цикла в графе. Докажите, что $\mu^* = \min_v\max_k\frac{d_n(v)-d_k(v)}{n-k}$, где $d_i(v)$ - длина кратчайшего пути из $s$ до $v$, содержащего ровно $i$ ребер.
57. Модифицируйте алгоритм Форда-Беллмана так, чтобы он находил в графе циклы минимального среднего веса за $O(VE)$ и $O(V^2)$ памяти.
58. Модифицируйте алгоритм Флойда, чтобы найти в графе отрицательный цикл.
59. Петя перепутал и написал в алгоритме Флойда "for i: for j: for k: relax(d[i][j], d[i][k]+d[k][j])". Постройте тест, на котором получившийся алгоритм работает неверно.
60. Петя перепутал и написал в алгоритме Флойда "for i: for j: for k: relax(d[i][j], d[i][k]+d[k][j])". Заметив, что это работает неверно, он запустил этот алгоритм два раза. Будет ли получившийся алгоритм "for t from 1 to 2: for i: for j: for k: relax(d[i][j], d[i][k]+d[k][j])" корректным?
61. В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла.
62. Теорема Оре: если для любых вершин $u$ и $v$, не соединенных ребром, сумма степеней $deg(u) + deg(v) \ge n$, то в графе существует Гамильтонов цикл. В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла.
63. В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла.
64. Харари 7.2
65. Харари 7.4
66. Харари 7.5
67. Харари 7.7
68. Харари 7.9
69. Харари 7.14
70. Харари 7.17
71. Харари 7.18
72. Посчитать хроматический многочлен цикла $C_n$
73. Посчитать хроматический многочлен колеса $C_n + K_1$.
74. Посчитать полного двудольного графа $K_{n,m}$.
75. Харари 12.2
76. Харари 12.3
77. Харари 12.4
78. Харари 12.5
79. Харари 12.6
80. Харари 12.12
81. Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
82. Доказать формулу Уитни: пусть $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$ рёбер.
83. Харари 11.1
84. Харари 11.2
85. Харари 11.3
86. Харари 11.7
87. Харари 11.8
88. Харари 11.9
89. Харари 11.10
90. Харари 11.14
91. Харари 11.15
92. Харари 11.25
93. Сформулируйте и докажите аналогичную лемме о сумме лемму о разности потоков.
94. Вспомните граф, показанный на лекции, где пропускные способности трех средних ребер 1, $\varphi$ и $\varphi^2$. Предложите последовательность дополняющих путей в этом графе, при выборе которых максимальный поток никогда не будет найден.
95. Будем жадно выбирать для дополнения путь с максимальной остаточной пропускной способностью. Докажите, что при этом в сети с целочисленными пропускными способностями время работы алгоритма будет $O(poly(V, E) \log(C_{max}))$, где $C_{max}$ - максимальная пропускная способность ребра, а $poly$ - некоторый полином.
96. Докажите теорему о декомпозиции: любой поток можно представить в виде $f = \sum c_if_{P_i} + \sum d_j f_{C_j}$, где $P_i$ - пути из s в t, $C_j$ - циклы, $f_{P_i}$ и $f_{C_j}$ - единичные потоки вдоль этих путей/циклов, $c_i$ и $d_j$ - константы.
97. Докажите, что для любых $V$ и $E$ ($E = O(V^2)$, $E = \Omega(V)$) существует граф с $V$ вершинами и $E$ ребрами, в котором любая декомпозиция любого максимального потока содержит $\Omega(E)$ слагаемых, каждое из которых есть путь/цикл длины $\Omega(V)$.
98. Поток назовём циркуляцией, если его величина равна 0. Пусть в графе $G$ заданы две функции на ребрах: $L: E\to \mathbb{R}$ и $R: E\to \mathbb{R}$. Будем называть циркуляцию допустимой, если $L(uv) \le f(uv) \le R(uv)$. Требуется свести задачу поиска допустимой циркуляции в сети к задаче о максимальном потоке.
99. Сведите задачу о максимальном потоке с несколькими истоками и несколькими стоками к обычной задаче о максимальном потоке.
100. Можно ввести понятие пропускной способности вершины $c(u)$ как максимальной разрешенной суммы $\sum_{uv}f(uv)$. Решите задачу о максимальном потоке для графа с пропускными способностями вершин.