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

1. Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее """"постройте граф с $n$ вершинами, ..."""" означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
2. Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Опишите все такие графы. Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$. Опишите все такие графы.
3. Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
4. Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
5. Докажите, что в графе число вершин нечетной степени четно. Докажите, что если в графе ровно две вершины нечетной степени, то они лежат в одной компоненте связности.
6. Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
7. В графе $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ равны тогда и только тогда, когда в графе $G$ есть ребро $uv$. Что можно сказать про граф $G$?
8. Граф называется кубическим, если степень всех вершин равна 3. Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
9. Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения. Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
10. Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на простом цикле. Доказать, что вершинная двусвязность - это $R^*$.
11. Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
12. Обозначим как $\delta(G)$ минимальную степень вершины $G$. Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
13. Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
14. Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
15. Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
16. Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
17. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями. Приведите пример графа, что ни он, ни его дополнение не связаны путями длины не больше 2.
18. Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
19. Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
20. Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
21. Докажите или опровергните, что в связном графе все простые пути, имеющие максимальную возможную длину в этом графе, имеют общую вершину.
22. Центром графа называется вершина $u$, для которой кратчайшее расстояние до наиболее удаленной от $u$ вершины минимально. Докажите, что у дерева не более двух центров.
23. Барицентром графа называется вершина $u$, сумма расстояний от которой до остальных вершин минимальна. Докажите, что у дерева не более двух барицентров.
24. Каждое дерево является двудольным графом. А какие деревья являются полными двудольными графами?
25. Докажите, что если $v$ точка сочленения в $G$, то $v$ не точка сочленения в $\overline G$.
26. Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.
27. Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?
28. Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами?
29. Диаметром графа называют максимальное значение кратчайшего пути между двумя его вершинами. Пусть связный граф $G$ имеет хотя бы 4 вершины и диаметр $d$. Докажите или опровергните, что у $G$ есть остовное дерево с диаметром $d$.
30. Рассмотрим множество остовных деревьев связного графа $G$. Построим граф $S_G$, вершинами которого являются остовные деревья $G$, а две вершины $T_1$ и $T_2$ соединены ребром, если дерево $T_2$ можно получить из $T_1$ удалением одного ребра и добавлением другого. Докажите, что $S_G$ является связным.
31. Докажите, что две вершины $T_1$ и $T_2$ в $S_G$ соединены ребром тогда и только тогда, когда их объединение содержит ровно один простой цикл.
32. Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$.
33. Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$.
34. Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$.
35. Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев.
36. Дан код Прюфера дерева. Найдите степень каждой вершины, не восстанавливая дерево явно.
37. Даны числа $d_1, d_2, \ldots, d_n$. Докажите, что количество деревьев, в которых $deg(1) = d_1$, ..., $deg(n) = d_n$ равно $\frac {(n-2)!} {\Pi (d_i - 1)!}$
38. Обобщение формулы Кэли. Пусть дан полный граф, и остовный лес в нём, компоненты связности леса состоят из $c_1, c_2, \ldots, c_k$ вершин. Докажите, что число способов добавить ребра, чтобы получилось остовное дерево, равно $c_1 c_2 \ldots c_k (c_1+c_2+\ldots+c_k)^{k-2}$.
39. Для $n \ge 2$, найдите формулу для количества остовных деревьев $K_n$, содержащих ребро $1 - 2$,
40. Обобщите матричную теорему Кирхгофа для следующей задачи: дан ориентированный граф и вершина $r$, нужно найти количество корневых деревьев с корнем в $r$.
41. Сколько раз необходимо оторвать карандаш от бумаги, чтобы нарисовать граф $K_n$, не проводя никакое ребро два раза, в зависимости от $n$?
42. Сколько раз необходимо оторвать карандаш от бумаги, чтобы нарисовать граф $K_{n,m}$, не проводя никакое ребро два раза, в зависимости от $n$ и $m$?
43. Докажите, что связный граф эйлеров тогда и только тогда, когда каждый его блок (компонента вершинной двусвязности) эйлеров
44. Сбалансированной ориентацией неориентированного графа называют такую ориентацию всех его ребер, чтобы в каждую вершину входило столько же ребер, сколько выходит. Какие графы имеют сбалансированную ориентацию?
45. Граф называется произвольно вычерчиваемым из вершины $u$, если следующая процедура всегда приводит к эйлеровому циклу: начиная с вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, по которому ранее не проходили. Докажите, что эйлеров граф является произвольно вычерчиваемым из $u$, если любой его простой цикл содержит $u$.
46. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то $u$ имеет максимальную степень в $G$.
47. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то либо $u$ - единственная точка сочленения в $G$, либо в $G$ нет точек сочленения.
48. Реберным графом для графа $G$ называется граф $G_E$, множество вершин которого совпадает с множеством ребер исходного графа, два ребра $e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. В каком случае ребра реберного графа можно разбить на полные подграфы таким образом, чтобы каждая вершина принадлежала в точности двум из подграфов?
49. Выразите число треугольников в реберном графе $G_E$ через число треугольников графа $G$ и набор его степеней.
50. В каком случае связный граф $G$ имеет регулярный реберный граф?
51. Постройте связный граф $G$ с $n \ge 4$ вершинами, для которого граф $G_E$ не эйлеров, а граф $(G_E)_E$ эйлеров.
52. Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $((G_E)_E)_E$ эйлеров, то $(G_E)_E$ эйлеров.
53. Сколько существует неизоморфных связных неориентированных эйлеровых графов с 4 вершинами?
54. Сколько существует неизоморфных связных неориентированных эйлеровых графов с 5 вершинами?
55. Сколько существует неизоморфных связных неориентированных эйлеровых графов с 6 вершинами?
56. Сколько эйлеровых циклов у $K_n$?
57. Ребра связного неориентированного графа раскрашены в 2 цвета: красный и синий, причем каждой вершине инцидентно равное число ребер красного и синего цвета. Докажите, что между любой парой вершин существует путь (не обязательно простой), в котором любые два соседних ребра имеют разные цвета.
58. На некоторых клетках таблицы $n\times n$ стоит фишка, причем в каждой горизонтали и в каждой вертикали стоит хотя бы две фишки. Докажите или опровергните, что можно убрать часть фишек, чтобы в каждой вертикали и в каждой горизонтали стояло ровно по две фишки.
59. Дан неориентированный регулярный граф, степень каждой вершины которого равна $k^2$. Звездой называется набор из $k$ ребер, инцидентных одной и той же вершине. Докажите или опровергните, что можно разбить все ребра этого графа на звезды.
60. Порожденным (также индуцированным) подграфом называется подграф, полученный удалением некоторого множества вершин и всех инцидентных ребер. Докажите или опровергните, что если $G$ содержит порожденный тета-подграф (две вершины, соединенные тремя путями длины хотя бы 2), то $G$ не гамильтонов.
61. Обозначим как $G^3$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 3. Докажите, что если $G$ связен, то $G^3$ гамильтонов.
62. Докажите, что каждое ребро $G^3$ принадлежит его некоторому простому циклу
63. Продемонстрируйте пример негамильтонова графа с 10 вершинами, где для любой пары несмежных вершил $u$ и $v$ сумма их ступеней хотя бы 9.
64. Граф называется произвольно гамильтоновым, если следующая процедура всегда приводит к гамильтонову циклу: начиная с произвольной вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, другой конец которого мы ранее не посещали, либо обратно в вершину $u$, если непосещенных соседей нет. Опишите все произвольно гамильтоновы графы.
65. Будем называть последовательность $(d_1, \ldots, d_n)$ степенной последовательностью, если существует граф с такими степенями вершин. Приведите критерий, проверяемый за полиномиальное время, что заданная последовательность является степенной.
66. Теорема "Антихватала". Докажите, что если для степенной последовательности не выполнено условие теоремы Хватала, то найдется граф со степенной последовательностью, мажорирующей данную, не содержащий гамильтонова цикла.
67. Теорема "Антидирака". Для любого $n \ge 3$ постройте граф, степень каждой вершины которого хотя бы $\lceil n / 2\rceil - 1$, который не является гамильтоновым.
68. Докажите, что если сумма степеней любых двух несмежных вершин графа $G$ не меньше $n+1$, то любые две различные вершины $G$ можно соединить гамильтоновым путем.
69. Докажите, что если в графе с $n$ вершинами хотя бы $(n^2-3n+6)/2$ ребер, то он гамильтонов
70. Реберным графом для графа $G$ называется граф $G_E$, множество вершин которого совпадает с множеством ребер исходного графа, два ребра $e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. Докажите или опровергните, что если $G$ является эйлеровым, то реберный граф является гамильтоновым.
71. Докажите или опровергните, что если $G_E$ является гамильтоновым, то граф $G$ является эйлеровым.
72. Постройте минимальный по числу ребер связный граф, рёберный граф которого не пуст и в реберном графе которого нет гамильтонова цикла.
73. Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий для каждого ребра графа $G$ хотя бы одну вершину, ему инцидентную.
74. Докажите усиленную версию теоремы Редеи-Камеона: в любом сильно связном турнире с $n$ вершинами есть простой цикл любой длины от $3$ до $n$.
75. Докажите, что в любом турнире существует вершина, из которой достижимы все остальные за не более, чем 2 шага
76. Рассмотрим все такие гамильтоновы графы, что после удаления любой вершины (и всех инцидентных ребер) он становится гамильтоновым. Докажите, что в таком графе хотя бы 10 вершин, постройте такой граф с 10 вершинами.
77. Обозначим как $\lambda(G)$ минимальное число ребер, которое нужно удалить в графе, чтобы он потерял связность, $\kappa(G)$ - минимальное число вершин, которое нужно удалить в графе, чтобы он потерял связность (для полного графа полагаем $\kappa(G)=n-1$). Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
78. Докажите. что для любых $1 \le \kappa(G) \le \lambda(G) \le \delta(G)$ существует граф $G$ с такими параметрами.
79. Докажите, что не существует графов с $\kappa(G) = 3$ и $7$ ребрами.
80. Пусть $G$ - полный двудольный граф, за исключением $K_{2,2}$. Докажите $\lambda(G)=\delta(G)$, почем единственный способ удалить $\lambda(G)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин.
81. Графы $G_1$, содержащий $n_1$ вершин и $m_1$ ребер, и $G_2$, содержащий $n_2$ вершин и $m_2$ ребер, гомеоморфны. Докажите, что $n_1+m_2 = n_2+m_1$.
82. Рассмотрим параметрически заданную замкнутую кривую $\phi(t)$, будем говорить, что она имеет самопересечение, если есть точка на кривой, которая порождается двумя различными значениями параметра $t_1$ и $t_2$, причем в окрестности этой точки фрагменты кривой в окрестности параметра $t_2$ лежат по разную сторону от кривой в окрестности параметра $t_1$. Докажите, что планарный эйлеров граф содержит эйлеров цикл, не имеющий самопересечений.
83. Приведите пример вершинно двухсвязного планарного графа, который не является гамильтоновым.
84. Докажите, что планарный четырехсвязный граф гамильтонов.
85. Пусть $G$ - связный планарный граф, в котором каждый треугольник ограничивает область, не содержащую ребер, причем добавление любого ребра нарушает его планарность. Докажите, что $G$ гамильтонов.
86. Докажите, что любой трехсвязный планарный граф имеет остов, у которого наибольшая степень равна 3.
87. Докажите, что все колеса самодвойственны.
88. Докажите, что в планарном графе $O(n)$ треугольников.
89. Докажите, что можно ориентировать ребра планарного графа так, что $deg^-(v) \le 5$ для всех вершин $v$.
90. Докажите, что можно ориентировать ребра планарного графа так, что $deg^-(v) \le 3$ для всех вершин $v$.
91. Уложите четырехмерный куб на поверхности тора
92. Уложите $K_7$ на поверхности тора
93. Докажите, что $K_8$ нельзя уложить на поверхности тора
94. Найдите максимальное $k$, что граф $K_k$ можно уложить на сфере с двумя ручками.
95. Докажите, что для любого $m$ существует $k$, такое что граф с $K_k$ нельзя уложить на сфере с $m$ ручками.
96. Посчитать хроматический многочлен цикла $C_n$
97. Посчитать хроматический многочлен колеса $C_n + K_1$.
98. Посчитать хроматический многочлен полного двудольного графа $K_{n,m}$.
99. Приведите пример двух связных графов, которые не являются деревьями, не являются изоморфными и имеют одинаковые хроматические многочлены.
100. Докажите, что если длина максимального простого нечетного цикла в $G$ есть $k$, то $\chi(G)\le k + 1$.
101. Если степени вершин графа $G$ равны $d_1 \ge d_2 \ge \ldots \ge d_n$, то $\chi(G)\le \max\min\{i, d_i+1\}$.
102. Докажите или опровергните, что если граф $G$ с $n$ вершинами содержит гамильтонов цикл, причем ему принадлежат не все ребра графа, то (а) $\chi(G) \le 1 + n/2$ (б) $\chi(G) \ge 1 + n/2$ .
103. Конъюнкцией $G_1 \wedge G_2$ графов называется граф с $V = V_1 \times V_2$, $(u_1, u_2)-(v_1, v_2) \in E$, если $u_1v_1 \in E_1$ и $u_2v_2\in E_2$. Доказать, что хроматическое число конъюнкции $G_1\wedge G_2$ графов $G_1$ и $G_2$ двух графов не превосходит хроматических чисел этих графов.
104. Рассмотрим связный граф $G$, не являющийся простым циклом нечетной длины, все простые циклы которого нечетны. Обозначим как $\chi'(G)$ минимальное число цветов, в которое можно раскрасить ребра граф $G$, чтобы ни в какую вершину не входило ребер одного цвета. Докажите, что $\chi'(G)=\Delta(G)$.
105. Докажите, что в любой раскраске реберного графа каждая вершина смежна не более чем с двумя вершинами одного цвета
106. Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
107. Доказать формулу Уитни: пусть $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$ рёбер.
108. Граф называется однозначно раскрашиваемым, если любые две его раскраски в $\chi(G)$ цветов совпадают с точностью до переименования цветов. Приведите пример однозначно раскрашиваемого связного графа и связного графа, который не является однозначно раскрашиваемым
109. Какое минимальное число вершин может быть в однозначно раскрашиваемом в 3 цвета графе, отличном от полного графа?
110. Какое минимальное число ребер может быть в однозначно раскрашиваемом в $k$ цветов графе с $n$ вершинами?
111. Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно?
112. Петя хочет упростить алгоритм Каргера-Штайна. Он запускает алгоритм Каргера (стягивание по случайному ребру), пока количество вершин не станет равно $t$, а затем запускает алгоритм за $t^3$ поиска минимального глобального разреза. Затем он повторяет алгоритм, пока вероятность успеха не составит хотя бы $1/2$. Какое значение $t$ необходимо выбрать, чтобы минимизировать время работы получившегося алгоритма? Какое будет время работы?
113. Докажите, что если в полном двоичном дереве высоты $h$ каждое ребро удаляется с вероятностью $1/2$, то путь от корня до листа сохраняется с вероятностью $\Theta(1/h)$.
114. Обобщите предыдущее задание, если ребро удаляется с вероятностью $p$.
115. С учетом предыдущего задания модифицируйте алгоритм Каргера-Штайна, чтобы разветвляться когда накопленная вероятность ошибки достигнет $p$. Найдите зависимость времени работы от $p$, какое значение $p$ оптимально выбрать?
116. Назовем разрез $\alpha$-оптимальным, если его размер не больше $\alpha C_{min}$, где $C_{min}$ - минимальный разрез. Оцените вероятность, что один запуск алгоритма Каргера (без разветвлений) найдет $\alpha$-оптимальный разрез (в зависимости от $\alpha$).
117. Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов.
118. Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов.