Список заданий по ДМ 2к 2016 осень

<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. Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
16. Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
17. Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
18. При каких соотношениях $a$, $b$, $n$, $m$, $k$ существует граф с $a$ точками сочленения, $b$ мостами, $n$ вершинами, $m$ рёбрами, $k$ компонентами связности?
19. Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это рефлексивно-транзитивное замыкание $R$.
20. Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
21. Харари 4.2
22. Харари 4.3
23. Харари 2.29
24. Харари 2.31
25. Харари 2.32
26. Харари 2.33
27. Харари 2.35
28. Харари 2.36
29. Харари 7.2
30. Харари 7.4
31. Харари 7.5
32. Харари 7.7
33. Харари 7.9
34. Харари 7.14
35. Харари 7.17
36. Харари 7.18
37. Харари 3.2
38. Наименьшее число вершин в кубическом графе, имеющем мост, равно 10. (Харари 3.3)
39. Харари 3.4
40. Харари 3.5
41. Харари 3.6
42. Харари 3.7
43. Харари 3.9
44. Посчитать хроматический многочлен цикла $C_n$
45. Посчитать хроматический многочлен колеса $C_n + K_1$.
46. Посчитать полного двудольного графа $K_{n,m}$.
47. Харари 12.2
48. Харари 12.3
49. Харари 12.4
50. Харари 12.5
51. Харари 12.6
52. Харари 12.12
53. Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
54. Доказать формулу Уитни: пусть $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$ рёбер.
55. Харари 11.1
56. Харари 11.2
57. Харари 11.3
58. Харари 11.7
59. Харари 11.8
60. Харари 11.9
61. Харари 11.10
62. Харари 11.14
63. Харари 11.15
64. Харари 11.25
65. Харари 9.1
66. Харари 9.3
67. Харари 9.4
68. Харари 9.5
69. Харари 9.8
70. Харари 9.9
71. Харари 9.13
72. Харари 8.1
73. Харари 8.2
74. Харари 8.3
75. Харари 8.8
76. Харари 8.9
77. Харари 8.10
78. Харари 8.11
79. Матроид с выкинутым элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Множества, не содержавшие $x$, остаются независимыми. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A | A \in I, x \not\in A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setminus x$ является матроидом.
80. Матроид, стянутый по элементу. Пусть $M$ - матроид. Обозначим как $M/x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются множества, которые ранее содержали $x$, после удаления из них этого элемента. Формально, если $M = \langle X, I\rangle$, то $M/x = \langle X \setminus x, \{A \setminus x | A \in I, x \in A\}\rangle$. Докажите, что для любых $M$ и $x$, таких что $\{x\}\in I$ получившаяся конструкция $M/x$ является матроидом.
81. Прямая сумма матроидов. Пусть $M_1 = \langle X_1, I_1\rangle$ и $M_2=\langle X_2, I_2\rangle$ - матроиды с непересекающимися носителями ($X_1 \cap X_2 = \varnothing$). Обозначим как $M_1+M_2$ следующую конструкцию: $M_1 + M_2 = \langle X_1 \cup X_2, I = \{A \cup B|A \in I_1, B \in I_2\}$. Докажите, что сумма матроидов является матроидом.
82. Разноцветные множества. Пусть $X$ - множество элементов, каждый из которых раскрашен в некоторый цвет. Будем называть независимыми множества, в которых все элементы разного цвета. Докажите, что эта конструкция является матроидом. Используйте определение матроида.
83. Представьте конструкцию из предыдущего примера в виде прямой суммы универсальных матроидов.
84. Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
85. Является ли венгерский алгоритм вариантом алгоритма Радо-Эдмондса?
86. Образуют ли паросочетания в полном графе семейство независимых множеств некоторого матроида?
87. Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
88. Верно ли, что в графовом матроиде любая база пересекается с любым циклом?
89. Верно ли, что в матричном матроиде любая база пересекается с любым циклом?
90. Верно ли, что в любом матроиде любая база пересекается с любым циклом?
91. Обратная аксиома баз. Докажите, что если $B_1$ и $B_2$ - базы матроида, то для любого $y \in B_2 \setminus B_1$ найдется $x \in B_1 \setminus B_2$, такой что $B_1 \setminus x \cup y$ тоже база.
92. Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую констркуцию: $M^* = \langle X, \{A | \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
93. Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом?
94. Урезанный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M|_k$ следующую констркуцию: $M|_k = \langle X, \{A | A \in I, |A| \le k \}\rangle$. Докажите, что $M|_k$ является матроидом.
95. Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксимомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
96. Пусть $M$ - предматроид. Как и в матроиде будем называть базой множества максимальное подмножество из $I$. Докажите, что если для каждого множества $A$ все его базы равномощны, то $M$ - матроид.
97. Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
98. Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $X = \{x_1, x_2, \ldots, x_n\}$. Пусть $Y = \left\{x_k \,|\, rank(\{x_1, \ldots, x_{k-1}, x_k\}) > rank(\{x_1, \ldots, x_{k-1}\})\right\}$. Докажите, что $Y$ независимо.
99. Какие универсальные матроиды являются матричными?
100. Докажите, что матроид Вамоса не является представимым ни над каким полем.
101. Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
102. Когда двойственный к графовому матроид является графовым?
103. Задан многочлен $A(x) = \sum\limits_{i=0}^n a_i x^i$ степени $n$ и точка $x_0$. Найдите представление $A(x)$ в виде $A(x) = q(x) \cdot (x - x_0) + r$, где $r$~--- число, а $q(x) $~--- многочлен степени $n-1$ за время $O(n)$.
104. Предложите способ восстановления коэффициентов многочлена $A(x) = \sum\limits_{i=0}^{n-1} a_i x^i$ по заданным $n$ парам $\{(x_0, y_0), (x_1, y_1), \ldots (x_{n-1}, y_{n-1})\}$, где $y_i = A(x_i)$ и все $x_i$ различны, за $O(n^2)$.
105. Докажите, что $DFT(DFT(\langle a_0, a_1, \ldots, a_{n-1} \rangle)) = n \cdot \langle a_0, a_{n-1}, a_{n-2}, \ldots, a_1 \rangle$
106. Опишите модификацию алгоритма FFT для случая, когда размер массива является степенью 3 ($n = 3^k$). Какое будет рекуррентное соотношение для времени работы и само время работы в таком случае? Указание: как разделить на 3 многочлена и как скомпоновать результаты?
107. Для заданных $n$ различных чисел $x_0, x_1, \ldots, x_{n-1}$ постройте многочлен $n$ степени, который имеет корни только в заданных $n$ точках за $O(n \log^2 n)$
108. Пусть мы хотим считать преобразование Фурье не в поле комплексных чисел, а в поле остатков по модулю $p$, где $p$~--- простое число. Для каких $p$ такое преобразование можно сделать, как найти соответствующий корень из единицы $\omega_n$, и как изменится сам алгоритм?
109. Даны две строки $p$ и $t$ из символов 0 и 1 ($|p| \le |t|$). Найдите расстояние Хэмминга между $p$ и всеми подстроками $t[i..i+|p|-1]$ длины $|p|$ за $O(n \log n)$.
110. Для всех чисел $n$ от 1 до $N$ посчитайте количество представлений вида $n = a\cdot b + c \cdot d$, $a, b, c, d > 0$ за $O(n \log n)$.
111. Задан многочлен $A(x) = \sum\limits_{i=0}^{2^k-1} a_i x^i, a_0 \neq 0$. Найдите такой многочлен $B(x)$, что $A(x) \times B(x) \equiv 1 \bmod (x^{2^k})$ за $O(n \log^2 n$ [hard].
112. То же самое за $O(n \log n)$ [very hard].

</wikitex>