Список заданий по ДМ 2к 2017 осень

<wikitex>

1. Постройте граф с $n$ вершинами и $m$ ребрами. Здесь и далее "постройте граф с $n$ вершинами, ..." означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
2. Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$.
3. Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$.
4. Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
5. Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
6. Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) > n$.
7. Постройте двудольный граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) > n$.
8. Пусть для двудольного графа выполнено условие: для любой пары не соединенных ребром вершин есть вершина, связанная с обеими этими вершинами. Как устроен такой граф?
9. Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
10. Граф называется кубическим, если степень всех вершин равна 3. Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
11. Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
12. Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
13. Граф $G$ с $n$ вершинами называется графом пересечений, если можно найти такие множества $U_i$, $i$ от 1 до $n$, что вершины $i$ и $j$ связаны ребром тогда и только тогда, когда $U_i \cap U_j \ne \varnothing$. Докажите, что любой граф является графом пересечений.
14. Числом пересечения графа $\omega(G)$ называется минимальная возможная мощность множества $S$, что граф $G$ является графом пересечений для множеств $U_i \subset S$. Опишите графы с $\omega(G) = 1$.
15. Приведите пример графа с $\omega(G) = 2$.
16. Приведите пример графа с $n$ вершинами, для которого $\omega(G) > n$.
17. Докажите, что для любого графа с $n$ вершинами, где $n \ge 4$, выполнено $\omega(G) \le n^2/4$.
18. Обозначим как $C_n$ цикл из $n$ вершин. Найдите $\omega(C_n)$.
19. Найдите асимптотическое поведение $\omega(\overline{C_n})$.
20. Колесом $C_n + K_1$ называется граф, состоящий из цикла, содержащего $n$ вершин, и еще одной вершины $u$, причем все вершины цикла соединены с $u$. Найдите $\omega(C_n + K_1)$.
21. Докажите, что каждый циклический путь нечетной длины содержит простой цикл.
22. Докажите или опровергните, что объединение двух любых простых путей из вершины $u$ в вершину $v$ содержит цикл.
23. Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
24. Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
25. Докажите или опровергните, что в связном графе все самые длинные простые пути имеют общую вершину.
26. Обозначим как $\delta(G)$ минимальную степень вершины в графе. Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
27. Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
28. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
29. Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем четных простых циклов.
30. Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
31. Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
32. Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
33. Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
34. Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это $R^*$.
35. Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
36. Каждое дерево является двудольным графом. А какие деревья являются полными двудольными графами?
37. Доказать, что следующие четыре утверждения для связного графа $G$ эквивалентны: (1) любое ребро является мостом (2) $G$ является деревом (3) любой блок $G$ является $K_2$ (4) любое непустое пересечение связных подграфов $G$ связно.
38. Доказать, что следующие четыре утверждения для связного графа $G$ эквивалентны: (1) $G$ содержит ровно один простой цикл (2) число вершин и ребер $G$ совпадает (3) $G$ можно превратить в дерево удалением ровно одного ребра (4) множество ребер $G$, которые не являются мостами, образуют один простой цикл.

</wikitex>