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

2013-10-02T07:54:01Z

217.66.157.62:

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

Некоторые задания можно найти в книге [http://www.ozon.ru/context/detail/id/4452506/ Харари, Теория графов]

# Доказать, что если из $u$ достижима $v$, то существует простой путь из $u$ в $v$.
# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
# Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
# Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?
# Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.
# Харари 2.3
# Харари 2.5
# Харари 2.9
# Харари 2.13
# Харари 2.15
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
# Харари 2.16
# Харари 2.20
# Доказать теорему об эквивалентности утверждений для точек сочленения.
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
# Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
# При каких соотношениях $a$, $b$, $n$, $m$, $k$ существует граф с $a$ точками сочленения, $b$ мостами, $n$ вершинами, $m$ рёбрами, $k$ компонентами связности?
# Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это рефлексивно-транзитивное замыкание $R$.
# Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
# Харари 3.2
# Харари 3.3
# Харари 3.4
# Харари 3.5
# Харари 3.6
# Рассмотрим неориентированный граф $G$. Запустим dfs, затем ориентируем рёбра дерева dfs $T$ от корня, а остальные - к корню. Доказать, что компоненты сильной связности в получившемся графе равны компонентам рёберной двусвязности в исходном графе
# Разработать алгоритм поиска компонент рёберной двусвязности, используя ровно один запуск dfs.
# Разработать алгоритм поиска компонент вершинной двусвязности, используя ровно один запуск dfs.
# Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2\not\in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
# Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2 \in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
# Петя неправильно написал алгоритм подсчёта up, делая up[u] = min(up[u], up[v]) даже если ребро uv - обратное. Будет ли у него работать поиск мостов?
# Петя неправильно написал алгоритм подсчёта up, делая up[u] = min(up[u], up[v]) даже если ребро uv - обратное. Будет ли у него работать поиск точек сочленения?
# В первом издании Кормена была ошибка. Там было сказано, что вершина v есть точка сочленения тогда и только тогда, когда (v - корень И у v ≥ 2 сына) ИЛИ (v - не корень И up[v] ≥ enter[v]). Приведите контрпример.
# Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле.
# Граф называется вершинно k-связным, если он остаётся связным после удаления любых (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле.
# Пусть $G$ - связный граф. Обозначим как $\kappa(G)$ - минимальное число вершин, которое необходимо удалить, чтобы граф потерял связность. (для полного графа это число равно n - 1), $\lambda(G)$ - минимальное число рёбер, которое необходимо удалить, чтобы граф потерял связность, $\delta(G)$ - минимальную степень в вершины в графе $G$. Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
# Докажите, что для любых $a$, $b$, $c$, таких что $1 \le a \le b \le c$, существует граф $G$, такой что $\kappa(G) = a$, $\lambda(G) = b$, $\delta(G) = c$.
# Харари 4.2
# Харари 5.5
# Харари 5.6
# В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла.
# Теорема Оре: если для любых вершин $u$ и $v$, не соединенных ребром, сумма степеней $deg(u) + deg(v) \ge n$, то в графе существует Гамильтонов цикл. В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла.
# В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла.
# Харари 7.2
# Харари 7.4
# Харари 7.5
# Харари 7.7
# Харари 7.9
# Харари 7.14
# Харари 7.17
# Харари 7.18
</wikitex>

Викиконспекты - Вклад участника [ru]

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