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

<wikitex>

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

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

1. Доказать, что если из $u$ достижима $v$, то существует простой путь из $u$ в $v$.
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. Доказать теорему об эквивалентности утверждений для точек сочленения.
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. Харари 3.2
22. Харари 3.3
23. Харари 3.4
24. Харари 3.5
25. Харари 3.6
26. Рассмотрим неориентированный граф $G$. Запустим dfs, затем ориентируем рёбра дерева dfs $T$ от корня, а остальные - к корню. Доказать, что компоненты сильной связности в получившемся графе равны компонентам рёберной двусвязности в исходном графе
27. Разработать алгоритм поиска компонент рёберной двусвязности, используя ровно один запуск dfs.
28. Разработать алгоритм поиска компонент вершинной двусвязности, используя ровно один запуск dfs.
29. Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2\not\in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
30. Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2 \in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
31. Петя неправильно написал алгоритм подсчёта up, делая up[u] = min(up[u], up[v]) даже если ребро uv - обратное. Будет ли у него работать поиск мостов?
32. Петя неправильно написал алгоритм подсчёта up, делая up[u] = min(up[u], up[v]) даже если ребро uv - обратное. Будет ли у него работать поиск точек сочленения?
33. В первом издании Кормена была ошибка. Там было сказано, что вершина v есть точка сочленения тогда и только тогда, когда (v - корень И у v ≥ 2 сына) ИЛИ (v - не корень И up[v] ≥ enter[v]). Приведите контрпример.
34. Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на цикле.
35. Граф называется вершинно k-связным, если он остаётся связным после удаления любых (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на цикле.
36. Пусть $G$ - связный граф. Обозначим как $\kappa(G)$ - минимальное число вершин, которое необходимо удалить, чтобы граф потерял связность. (для полного графа это число равно n - 1), $\lambda(G)$ - минимальное число рёбер, которое необходимо удалить, чтобы граф потерял связность, $\delta(G)$ - минимальную степень в вершины в графе $G$. Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
37. Докажите, что для любых $a$, $b$, $c$, таких что $1 \le a \le b \le c$, существует граф $G$, такой что $\kappa(G) = a$, $\lambda(G) = b$, $\delta(G) = c$.
38. Харари 4.2
39. Харари 5.5
40. Харари 5.6
41. В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла.
42. Теорема Оре: если для любых вершин $u$ и $v$, не соединенных ребром, сумма степеней $deg(u) + deg(v) \ge n$, то в графе существует Гамильтонов цикл. В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла.
43. В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла.
44. Харари 7.2
45. Харари 7.4
46. Харари 7.5
47. Харари 7.7
48. Харари 7.9
49. Харари 7.14
50. Харари 7.17
51. Харари 7.18

</wikitex>