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

<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

</wikitex>