Список заданий по ДМ 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

</wikitex>