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

Материал из Викиконспекты
Перейти к: навигация, поиск

<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>