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

1. Во всех задачах этой серии графы неориентированные, ребро соединяет две различные вершины, между парой вершин есть не более одного ребра. Какое максимальное число ребер может быть в графе с $n$ вершинами?
2. Какое максимальное число ребер может быть в графе с $n$ вершинами и $k$ компонентами связности?
3. Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее «постройте граф с $n$ вершинами, ...» означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
4. Обозначим как $N(u)$ множество соседей вершины $u$, а как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Опишите все такие графы. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$. Опишите все такие графы.
5. Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
6. Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
7. Докажите, что в графе число вершин нечетной степени четно.
8. Для заданных $n$, $d$ и $D$ постройте граф с $n$ вершинами, в котором $\delta(G) = d$, $\Delta(G) = D$.
9. Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
10. В графе $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ равны тогда и только тогда, когда в графе $G$ есть ребро $uv$. Что можно сказать про граф $G$?
11. Граф называется кубическим, если степень всех вершин равна 3. Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
12. Постройте граф с $n$ вершинами и максимальным числом ребер, не содержащий треугольников.
13. Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Сколько внутренних автоморфизмов у полного графа $K_n$?
14. Будем называть внутренний автоморфизм тривиальным, если $\varphi(u)=u$. Постройте граф, который не имеет внутренних автоморфизмов, кроме тривиального, содержащий минимальное число вершин.
15. Вершина графа называется висячей, если она имеет степень $1$. Постройте граф, не имеющий внутренних автоморфизмов, кроме тривиального, у которого нет висячих вершин.
16. Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
17. Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
18. Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это $R^*$.
19. Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
20. Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
21. Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
22. Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
23. Докажите или опровергните, что в связном графе (а) любые два пути имеющие максимальную возможную длину в этом графе, имеют общую вершину. (б) Верно ли что все самые длинные простые пути обязательно имеют общую вершину?
24. Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
25. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями. Приведите пример графа, что ни он, ни его дополнение не связаны путями длины не больше 2.
26. Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем нечётных простых циклов.
27. Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем чётных простых циклов.
28. Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
29. Центром графа называется вершина $u$, для которой кратчайшее расстояние до наиболее удаленной от $u$ вершины минимально. Докажите, что у дерева не более двух центров.
30. Барицентром графа называется вершина $u$, сумма расстояний от которой до остальных вершин минимальна. Докажите, что у дерева не более двух барицентров.
31. Каждое дерево является двудольным графом. А какие деревья являются полными двудольными графами?
32. Докажите, что если $v$ точка сочленения в $G$, то $v$ не точка сочленения в $\overline G$.
33. Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.
34. Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?
35. Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами?
36. Диаметром графа называют максимальное значение кратчайшего пути между двумя его вершинами. Пусть связный граф $G$ имеет хотя бы 4 вершины и диаметр $d$. Докажите или опровергните, что у $G$ есть остовное дерево с диаметром $d$.
37. Рассмотрим множество остовных деревьев связного графа $G$. Построим граф $S_G$, вершинами которого являются остовные деревья $G$, а две вершины $T_1$ и $T_2$ соединены ребром, если дерево $T_2$ можно получить из $T_1$ удалением одного ребра и добавлением другого. Докажите, что $S_G$ является связным.
38. Докажите, что две вершины $T_1$ и $T_2$ в $S_G$ соединены ребром тогда и только тогда, когда их объединение содержит ровно один простой цикл.
39. Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$.
40. Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев.
41. Даны числа $d_1, d_2, \ldots, d_n$. Докажите, что количество деревьев, в которых $deg(1) = d_1$, ..., $deg(n) = d_n$ равно $\frac {(n-2)!} {\Pi (d_i - 1)!}$
42. Обобщение формулы Кэли. Пусть дан полный граф, и остовный лес в нём, компоненты связности леса состоят из $c_1, c_2, \ldots, c_k$ вершин. Докажите, что число способов добавить ребра, чтобы получилось остовное дерево, равно $c_1 c_2 \ldots c_k (c_1+c_2+\ldots+c_k)^{k-2}$.
43. Для $n \ge 2$, найдите формулу для количества остовных деревьев $K_n$, содержащих ребро $1 -- 2$,
44. Сколько раз необходимо оторвать карандаш от бумаги, чтобы нарисовать граф $K_n$, не проводя никакое ребро два раза, в зависимости от $n$?
45. Сколько раз необходимо оторвать карандаш от бумаги, чтобы нарисовать граф $K_{n,m}$, не проводя никакое ребро два раза, в зависимости от $n$ и $m$?
46. Докажите, что связный граф эйлеров тогда и только тогда, когда каждый его блок (компонента вершинной двусвязности) эйлеров
47. Сбалансированной ориентацией неориентированного графа называют такую ориентацию всех его ребер, чтобы в каждую вершину входило столько же ребер, сколько выходит. Какие графы имеют сбалансированную ориентацию?
48. Граф называется произвольно вычерчиваемым из вершины $u$, если следующая процедура всегда приводит к эйлеровому циклу: начиная с вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, по которому ранее не проходили. Докажите, что эйлеров граф является произвольно вычерчиваемым из $u$, если любой его простой цикл содержит $u$.
49. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то $u$ имеет максимальную степень в $G$.
50. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то либо $u$ - единственная точка сочленения в $G$, либо в $G$ нет точек сочленения.
51. Реберным графом для графа $G$ называется граф $G_E$, множество вершин которого совпадает с множеством ребер исходного графа, два ребра $e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. В каком случае ребра реберного графа можно разбить на полные подграфы таким образом, чтобы каждая вершина принадлежала в точности двум из подграфов?
52. Выразите число треугольников в реберном графе $G_E$ через число треугольников графа $G$ и набор его степеней.
53. В каком случае связный граф $G$ имеет регулярный реберный граф?
54. Постройте связный граф $G$ с $n \ge 4$ вершинами, для которого граф $G_E$ не эйлеров, а граф $(G_E)_E$ эйлеров.
55. Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $((G_E)_E)_E$ эйлеров, то $(G_E)_E$ эйлеров.
56. Сколько существует неизоморфных связных неориентированных эйлеровых графов с 4 вершинами?
57. Сколько существует неизоморфных связных неориентированных эйлеровых графов с 5 вершинами?
58. Сколько существует неизоморфных связных неориентированных эйлеровых графов с 6 вершинами?
59. Сколько эйлеровых циклов у полного ориентированного графа с $n$ вершинами (в каждую сторону между любой парой различных вершин есть ребро)?
60. Ребра связного неориентированного графа раскрашены в 2 цвета: красный и синий, причем каждой вершине инцидентно равное число ребер красного и синего цвета. Докажите, что между любой парой вершин существует путь (не обязательно простой), в котором любые два соседних ребра имеют разные цвета.
61. На некоторых клетках таблицы $n\times n$ стоит фишка, причем в каждой горизонтали и в каждой вертикали стоит хотя бы две фишки. Докажите или опровергните, что можно убрать часть фишек, чтобы в каждой вертикали и в каждой горизонтали стояло ровно по две фишки.
62. Дан неориентированный регулярный граф, степень каждой вершины которого равна $k^2$. Звездой называется набор из $k$ ребер, инцидентных одной и той же вершине. Докажите или опровергните, что можно разбить все ребра этого графа на звезды.