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

1. Во всех задачах этой серии графы неориентированные, ребро соединяет две различные вершины, между парой вершин есть не более одного ребра. Какое максимальное число ребер может быть в графе с $n$ вершинами?
2. Какое максимальное число ребер может быть в графе с $n$ вершинами и двумя компонентами связности?
3. Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее ""постройте граф с $n$ вершинами, ..."" означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
4. Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Опишите все такие графы.
5. Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$. Опишите все такие графы.
6. Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
7. Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
8. Докажите, что в графе число вершин нечетной степени четно.
9. Докажите, что если в графе ровно две вершины нечетной степени, то они лежат в одной компоненте связности.
10. Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Для заданных $n$ и $k$ постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) = k$.
11. Для заданных $n$, $d$ и $D$ постройте граф с $n$ вершинами, в котором $\delta(G) = d$, $\Delta(G) = D$.
12. Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
13. В графе $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ равны тогда и только тогда, когда в графе $G$ есть ребро $uv$. Что можно сказать про граф $G$?
14. Граф называется кубическим, если степень всех вершин равна 3. Какое минимальное число вершин может быть в кубическом графе?
15. Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
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. Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
24. Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
25. Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
26. Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
27. Докажите или опровергните, что в связном графе все простые пути, имеющие максимальную возможную длину в этом графе, имеют общую вершину.
28. Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
29. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
30. Приведите пример графа, что ни он, ни его дополнение не связаны путями длины не больше 2.
31. Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем нечётных простых циклов.
32. Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем чётных простых циклов.
33. Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
34. Центром графа называется вершина $u$, для которой кратчайшее расстояние до наиболее удаленной от $u$ вершины минимально. Докажите, что у дерева не более двух центров.
35. Барицентром графа называется вершина $u$, сумма расстояний от которой до остальных вершин минимальна. Докажите, что у дерева не более двух барицентров.
36. Каждое дерево является двудольным графом. А какие деревья являются полными двудольными графами?
37. Докажите, что если $v$ точка сочленения в $G$, то $v$ не точка сочленения в $\overline G$.
38. Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.
39. Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?
40. Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами?
41. Диаметром графа называют максимальное значение кратчайшего пути между двумя его вершинами. Пусть связный граф $G$ имеет хотя бы 4 вершины и диаметр $d$. Докажите или опровергните, что у $G$ есть остовное дерево с диаметром $d$.
42. Рассмотрим множество остовных деревьев связного графа $G$. Построим граф $S_G$, вершинами которого являются остовные деревья $G$, а две вершины $T_1$ и $T_2$ соединены ребром, если дерево $T_2$ можно получить из $T_1$ удалением одного ребра и добавлением другого. Докажите, что $S_G$ является связным.
43. Докажите, что две вершины $T_1$ и $T_2$ в $S_G$ соединены ребром тогда и только тогда, когда их объединение содержит ровно один простой цикл.
44. Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$.
45. Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$.
46. Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$.
47. Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев.
48. Обобщение формулы Кэли. Пусть дан полный граф, и остовный лес в нём, компоненты связности леса состоят из $c_1, c_2, \ldots, c_k$ вершин. Докажите, что число способов добавить ребра, чтобы получилось остовное дерево, равно $c_1 c_2 \ldots c_k (c_1+c_2+\ldots+c_k)^{k-2}$.
49. Для $n \ge 2$, найдите формулу для количества остовных деревьев $K_n$, содержащих ребро $1 - 2$,
50. Дан код Прюфера дерева. Найдите степень каждой вершины, не восстанавливая дерево явно.
51. Даны числа $d_1, d_2, \ldots, d_n$. Докажите, что количество деревьев, в которых $deg(1) = d_1$, ..., $deg(n) = d_n$ равно $\frac {(n-2)!} {\prod (d_i - 1)!}$
52. Обобщите матричную теорему Кирхгофа для следующей задачи: дан ориентированный граф и вершина $r$, нужно найти количество корневых деревьев с корнем в $r$.
53. Граф называется произвольно вычерчиваемым из вершины $u$, если следующая процедура всегда приводит к эйлеровому циклу: начиная с вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, по которому ранее не проходили. Докажите, что эйлеров граф является произвольно вычерчиваемым из $u$, если любой его простой цикл содержит $u$.
54. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то $u$ имеет максимальную степень в $G$.
55. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то либо $u$ - единственная точка сочленения в $G$, либо в $G$ нет точек сочленения.
56. Порожденным (также индуцированным) подграфом называется подграф, полученный удалением некоторого множества вершин и всех инцидентных ребер. Докажите или опровергните, что если $G$ содержит порожденный тета-подграф (две вершины, соединенные тремя путями произвольной длины), то $G$ не гамильтонов.
57. Обозначим как $G^3$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 3. Докажите, что если $G$ связен, то $G^3$ гамильтонов.
58. Граф называется произвольно гамильтоновым, если следующая процедура всегда приводит к гамильтонову циклу: начиная с произвольной вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, другой конец которого мы ранее не посещали, либо обратно в вершину $u$, если непосещенных соседей нет. Опишите все произвольно гамильтоновы графы.
59. Будем называть последовательность $(d_1, \ldots, d_n)$ степенной последовательностью, если существует граф с такими степенями вершин. Приведите критерий, проверяемый за полиномиальное время, что заданная последовательность является степенной.
60. Теорема "Антихватала". Докажите, что если для степенной последовательности не выполнено условие теоремы Хватала, то найдется граф со степенной последовательностью, мажорирующей данную, не содержащий гамильтонова цикла.
61. Докажите, что если сумма степеней любых двух несмежных вершин графа $G$ не меньше $n+1$, то любые две различные вершины $G$ можно соединить гамильтоновым путем.
62. Реберным графом для графа $G$ называется граф $G_E$, множество вершин которого совпадает с множеством ребер исходного графа, два ребра $e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. Докажите или опровергните, что если $G$ является эйлеровым, то реберный граф является гамильтоновым.
63. Докажите или опровергните, что если $G_E$ является гамильтоновым, то граф $G$ является эйлеровым.
64. В каком случае ребра реберного графа можно разбить на полные подграфы таким образом, чтобы каждая вершина принадлежала в точности двум из подграфов?
65. Выразите число треугольников в реберном графе $G_E$ через число треугольников графа $G$ и набор его степеней.
66. В каком случае связный граф $G$ имеет регулярный реберный граф?
67. Постройте связный граф $G$ с $n \ge 4$ вершинами, для которого граф $G_E$ не эйлеров, а граф $(G_E)_E$ эйлеров.
68. Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $((G_E)_E)_E$ эйлеров, то $(G_E)_E$ эйлеров.
69. Постройте минимальный по числу ребер граф, в реберном графе которого нет гамильтонова цикла.
70. Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий для каждого ребра графа $G$ хотя бы одну вершину, ему инцидентную.
71. Обозначим как $\lambda(G)$ минимальное число ребер, которое нужно удалить в графе, чтобы он потерял связность, $\kappa(G)$ - минимальное число вершин, которое нужно удалить в графе, чтобы он потерял связность (для полного графа полагаем $\kappa(G)=n-1$). Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
72. Докажите. что для любых $1 \le \kappa(G) \le \lambda(G) \le \delta(G)$ существует граф $G$ с такими параметрами.
73. Докажите, что не существует графов с $\kappa(G) = 3$ и $7$ ребрами.
74. Пусть $G$ - полный двудольный граф, за исключением $K_{2,2}$. Докажите $\lambda(G)=\delta(G)$, почем единственный способ удалить $\lambda(G)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин.
75. Графы $G_1$, содержащий $n_1$ вершин и $m_1$ ребер, и $G_2$, содержащий $n_2$ вершин и $m_2$ ребер, гомеоморфны. Докажите, что $n_1+m_2 = n_2+m_1$.
76. Рассмотрим параметрически заданную замкнутую кривую $\phi(t)$, будем говорить, что она имеет самопересечение, если есть точка на кривой, которая порождается двумя различными значениями параметра $t_1$ и $t_2$, причем в окрестности этой точки фрагменты кривой в окрестности параметра $t_2$ лежат по разную сторону от кривой в окрестности параметра $t_1$. Докажите, что планарный эйлеров граф содержит эйлеров цикл, не имеющий самопересечений.
77. Приведите пример вершинно двухсвязного планарного графа, который не является гамильтоновым.
78. Докажите, что планарный четырехсвязный граф гамильтонов.
79. Пусть $G$ - планарный граф, в котором каждый треугольник ограничивает область, не содержащую ребер, причем добавление любого ребра нарушает это свойство. Докажите, что $G$ гамильтонов.
80. Докажите, что любой трехсвязный планарный граф имеет остов, у которого наибольшая степень равна 3.
81. Докажите, что все колеса самодвойственны.
82. Докажите, что в планарном графе $O(n)$ треугольников.
83. Докажите, что можно ориентировать ребра планарного графа так, что $deg^-(v) \le 5$ для всех вершин $v$.
84. Докажите, что можно ориентировать ребра планарного графа так, что $deg^-(v) \le 3$ для всех вершин $v$.
85. Уложите четырехмерный куб на поверхности тора
86. Уложите $K_7$ на поверхности тора
87. Докажите, что $K_8$ нельзя уложить на поверхности тора
88. Найдите максимальное $k$, что граф $K_k$ можно уложить на сфере с двумя ручками.
89. Докажите, что для любого $m$ существует $k$, такое что граф с $K_k$ нельзя уложить на сфере с $m$ ручками.
90. Посчитать хроматический многочлен цикла $C_n$
91. Посчитать хроматический многочлен колеса $C_n + K_1$.
92. Посчитать хроматический многочлен полного двудольного графа $K_{n,m}$.
93. Докажите, что если хроматический многочлен графа равен $t(t-1)^{n - 1}$, то граф является деревом.
94. Приведите пример двух связных графов, которые не являются деревьями, не являются изоморфными и имеют одинаковые хроматические многочлены.
95. Докажите, что если длина максимального простого нечетного цикла в $G$ есть $k$, то $\chi(G)\le k + 1$.
96. Если степени вершин графа $G$ равны $d_1 \ge d_2 \ge \ldots \ge d_n$, то $\chi(G)\le \max\min\{i, d_i+1\}$.
97. Докажите или опровергните, что если граф $G$ с $n$ вершинами содержит гамильтонов цикл, причем ему принадлежат не все ребра графа, то (а) $\chi(G) \le 1 + n/2$ (б) $\chi(G) \ge 1 + n/2$ .
98. Конъюнкцией $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$ двух графов не превосходит хроматических чисел этих графов.
99. Рассмотрим связный граф $G$, не являющийся простым циклом нечетной длины, все простые циклы которого нечетны. Обозначим как $\chi'(G)$ минимальное число цветов, в которое можно раскрасить ребра граф $G$, чтобы ни в какую вершину не входило ребер одного цвета. Докажите, что $\chi'(G)=\Delta(G)$.
100. Докажите, что в любой раскраске реберного графа каждая вершина смежна не более чем с двумя вершинами одного цвета
101. Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
102. Доказать формулу Уитни: пусть $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$ рёбер.
103. Граф называется однозначно раскрашиваемым, если любые две его раскраски в $\chi(G)$ цветов совпадают с точностью до переименования цветов. Приведите пример однозначно раскрашиваемого связного графа и связного графа, который не является однозначно раскрашиваемым
104. Какое минимальное число вершин может быть в однозначно раскрашиваемом в 3 цвета графе, отличном от полного графа?
105. Какое минимальное число ребер может быть в однозначно раскрашиваемом в $k$ цветов графе с $n$ вершинами?
106. Докажите, что существует такое $\alpha>1$, что у любого планарного графа c $n$ есть хотя бы $\alpha^n$ раскрасок в 5 цветов.
107. Доказать или опровернгнуть: любое вершинное покрытие содержит как подмножество минимальное по мощности вершинное покрытие.
108. Докажите, что $\alpha(G) \ge \frac{n}{1+\Delta(G)}$.
109. Докажите, что $\alpha(G) \ge \sum (1 + \deg u)^{-1}$.
110. Как может поменяться $\alpha(G)$ при удалении ребра? Удалении вершины? Добавлении ребра?
111. Верно ли, что для двудольного графа значение $\alpha(G)$ равно размеру максимальной доли?
112. Докажите, что $G$ двудольный тогда и только тогда, когда для любого $H$ - подграфа $G$ выполнено $\alpha(H) \ge |VH|/2$ ($VH$ - множество вершин графа $H$).
113. Докажите, что если в дереве расстояние между двумя любыми листьями четно, то в нем существует единственное максимальное по числу вершин независимое множество. Верно ли обратное?
114. Зафиксируем $n$ и $k$. Рассмотрим граф, удовлетворяющий следующим условиям: (1) граф $G$ содержит $n$ вершин; (2) $\alpha(G) \le k$. Среди таких графов рассмотрим граф с минимальным числом ребер. Этот граф называется граф Турана. Докажите, что в графе Турана любые две смежные вершины имеют равную степень.
115. Степень любых двух несмежных вершин в графе Турана отличается не более чем на $1$.
116. Оцените, сколько ребер в графе Турана.
117. Граф называется $\alpha$-критическим, если удаление любого ребра увеличивает $\alpha(G)$. Приведите пример $\alpha$-критического и не $\alpha$-критического графа.
118. Докажите, что в любом дереве, кроме $K_2$ существует минимальное по числу вершин вершинное покрытие, включающее все вершины, соседние с листьями.
119. Доминирующим множеством в графе называется множество вершин, такое что каждая вершина либо входит в это множество, либо имеет соседа в этом множестве. Докажите, что независимое множество вершин является максимальным по включению если и только если оно является доминирующим.
120. Обозначим размер минимального доминирующего множества в графе как $\gamma(G)$. Как связаны $\alpha(G)$ и $\gamma(G)$?
121. Докажите, что если в графе $G$ нет изолированных вершин, и $A$ - минимальное по включению доминирующее множество в $G$, то существует $B$, не имеющее общих вершин с $A$, также являющееся минимальным по включению доминирующим множеством в $G$.
122. Обозначим размер минимального по мощности покрывающего множества в графе как $\beta(G)$. Как связаны $\gamma(G)$ и $\beta(G)$?
123. Пусть $G$ - связный кубический граф, в котором не более двух мостов. Тогда в $G$ существует совершенное паросочетание.
124. Приведите пример связного кубического графа, содержащего три моста, в котором нет совершенного паросочетания.
125. $k$-факторизацией графа называется разбиение множество ребер графа на его $k$-факторы. Докажите, что $K_4$ имеет единственную 1-факторизацию.
126. Найдите число $1$-факторизаций графа $K_6$.
127. Найдите число $1$-факторизаций графа $K_{3,3}$.
128. Найдите число $1$-факторов графа $K_{2n}$.
129. Докажите, что граф $K_{6n-2}$ имеет 3-факторизацию.
130. Докажите, что граф $K_{4n+1}$ имеет 4-факторизацию.
131. Докажите, что граф $K_9$ представим в виде объединения 4 гамильтоновых циклов.
132. Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Пусть $G'$ получен из $G$ удалением не более чем $k - 1$ ребер. Тогда $G'$ содержит совершенное паросочетание. Указание: используйте теорему Татта.
133. Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Тогда для любого ребра $uv$ существует совершенное паросочетание, содержащее $uv$.
134. Докажите, что если $G$ - регулярный граф четной степени, то у него есть 2-фактор.
135. Пусть $r<k$ и хотя бы одно из них нечетно. Докажите, что существует $G$ - регулярный граф степени $k$, у которого нет $r$-фактора.
136. Множество $S\subset V$, для которого $odd(G\setminus S)-|S|=def(G)$, называется барьером. $A(G)$ является барьером графа. Приведите пример графа, в котором $A(G)$ не является максимальным по включению барьером.
137. Приведите пример графа, в котором $A(G)$ не является минимальным по включению барьером.
138. Докажите, что пересечение двух максимальных по включению барьеров также является барьером.
139. Пусть $x\in A(G)\cup C(G)$, $G'=G\setminus x$, $B'$ - барьер графа $G'$. Докажите, что $B=B'\cup x$ - барьер графа $G$. Следствие: любая вершина из $A(G) \cup C(G)$ входит в барьер графа $G$.
140. Пусть $B$ - барьер графа $G$, тогда $B\cap D(G)$ пусто и все компоненты $D(G)$ являются подмножествами нечетных компонент связности графа $G\setminus B$.
141. Пусть $B$ - барьер графа $G$, причем $x \in B$. Тогда $B' = B \setminus x$ - барьер графа $G' = G \setminus x$.
142. Докажите, что пересечение всех максимальных по включению барьеров $G$ равно $A(G)$.
143. Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
144. Докажите, что если связный граф $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
145. Найдите математическое ожидание и дисперсию степени вершины в биномиальной модели $G(n, p)$.
146. Равномерная модель $G(n, m)$ - каждый граф с $n$ вершинами и $m$ ребрами равновероятен. Найдите математическое ожидание степени вершины в равномерной модели $G(n, m)$.
147. Найдите дисперсию степени вершины в равномерной модели $G(n, m)$.
148. Найдите вероятность, что граф в равномерной модели $G(n, m)$ является деревом ($m = n - 1$).
149. Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является деревом.
150. Найдите вероятность, что граф в равномерной модели $G(n, m)$ является гамильтоновым циклом ($m = n$).
151. Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является гамильтоновым циклом.
152. Оцените центральный биномиальный коэффициент ${2n \choose n}$ снизу величиной порядка $c \frac {4^n}{\sqrt{n}}$, используя формулу Стирлинга.
153. Рассмотрим число ребер $m$, такое что $m(n) \to \infty$ и ${n \choose 2} - m(n) \to \infty$, а также $p(n) = \frac {m(n)}{n \choose 2}$. Докажите, что вероятность того, что $G(n, p)$ имеет ровно $m$ ребер есть $\Omega(m^{-0.5})$.
154. Рассмотрим свойство $A$, а и такие же $m(n)$ и $p(n)$, как в предыдущей задаче. Докажите, что $P(G(n, m) \in A) \le C \sqrt{m} P(G(n, p) \in A)$.
155. Рассмотрим следующую модель генерации случайного графа. Сначала проведем каждое ребро с вероятностью $\frac 12$. Затем, для каждой пары вершин, между которыми не было проведено ребро на первом шаге, проведем ребро с вероятностью $\frac 13$. Предложите более простое описание этой модели в терминах моделей Эрдёша-Реньи.
156. Свойство случайного графа называется, монотонным, если оно сохраняется при добавлении ребра. Рассмотрим монотонное свойство $A$ при фиксированном размере графа $n$. Докажите, что $P(G(n, p) \in A)$ возрастает при возрастании $p$.
157. Придумайте такое свойство, что вероятность, что $G(n, \frac 12)$ обладает этим свойством, стремится к $\frac 14$.
158. Придумайте такое свойство, что вероятность, что $G(n, \frac 12)$ обладает этим свойством, стремится к $\frac 13$.
159. Пусть для некоторого свойства $A$ существует две функции $p_1(n)$ и $p_2(n)$, что для графа $G(n, p_1(n))$ свойство $A$ а.п.н. не выполняется, а для $G(n, p_2(n))$ свойство $A$ а.п.н. выполняется. Докажите, что существует функция $\tilde p(n)$, что для случайного графа $G(n, \tilde p(n))$ свойство $A$ выполняется с вероятностью, стремящейся к $\frac 12$.
160. Подберите $p(n)$ и приведите последовательности случайных величин $X_n$ для $G(n, p)$, что $EX_n \to \infty$, но $\mathcal{P}(X_n = 0) \nrightarrow 0$.
161. Докажите, что $G(n, \frac {2\ln n}{n})$ а.п.н. не содержит вершин степени 0.
162. Рассмотрим модель случайного двудольного графа $G(n, n, p)$: из полного двудольного графа $K_{n,n}$ каждое ребро удаляется с вероятностью $1 - p$. Пусть $X$ -- количество изолированных вершин первой доли. Найдите $EX$ и $DX$.
163. Докажите, что если $p = o(n^{-1.5})$, то $G(n, p)$ а.п.н. является объединением компонент связности размера 1 и 2.
164. Докажите, что если $p = \omega(n^{-1.5})$, то $G(n, p)$ а.п.н. содержит путь длины 2.
165. Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$.
166. Пусть $p = o(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. не содержит цикл длины $k$.
167. Пусть $p = \omega(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$.
168. Пусть $p = o(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. не содержит циклов.
169. Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}n)$?
170. Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {\ln n}{2n})$ стремится к бесконечности.
171. Найдите матожидание количества индуцированных подграфов $G(n, \frac dn)$, $d > 1$, которые являются путем длины $k = \sqrt{\log n}$.
172. Для каких $p$ граф $G(n, p)$ а.п.н. не содержит $K_k$ (надо привести пороговую асимптотику)?
173. Пусть $p = \frac dn$. Докажите, что в $G(n, p)$ каждая вершина а.п.н. принадлежит не более, чем одному треугольнику.
174. Докажите, что в $G(n, \frac 12)$ а.п.н. не существует независимого множества размера $2 \log_2 n$
175. Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.
176. Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$.
177. Найдите пороговую асимптотику, что граф $G(n, p)$ является эйлеровым или докажите, что её не существует
178. Докажите, что если $k = \frac{\log n}{\log\log n}$, то $k! \le n$.
179. Покажите, что в первой доле случайного двудольного графа $G(n, n, 1/n)$ с вероятностью, не стремящейся к нулю, существует вершина степени $\frac{\log n}{\log \log n}$.
180. Зачем условие двудольности в предыдущей задаче? Покажите, что его можно убрать, в случайном графе $G(n, 1/n)$ с вероятностью, не стремящейся к нулю, существует вершина степени $\frac{\log n}{\log \log n}$.
181. Докажите, что $G(n, 1/n)$ а.п.н. не содержит вершины степени больше $\frac{6\log n}{\log \log n}$. Указание, используйте приближение биномиального распределения Пуассоном и факт, что $k! \ge (k/e)^k$.
182. Пусть $p = \frac dn$. Что можно сказать про наличие циклов в $G(n, p)$ в зависимости от $d$?
183. Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = \omega(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. содержит полное паросочетание. Указание: используйте лемму Холла.
184. Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = o(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. не содержит полное паросочетание. Указание: используйте лемму Холла.
185. Пусть $p = \frac{\ln n + c}{n}$. Какой предел вероятности, что у $G(n,p)$ ровно $k$ изолированных вершин?
186. Петя пытается спрятать в случайном графе клику размера $k$. Он берет граф с $n$ вершинами, $k$ из которых образуют клику, а остальных ребер нет, после чего проводит каждое из оставшихся ребер с вероятностью $1/2$. Вася хочет найти спрятанную Петей клику - выяснить, какие вершины ее образовывали. Для этого он выбирает $k$ вершин максимальной степени. Докажите, что если $k = \omega(\sqrt{n \ln n})$, то Вася а.п.н. найдет спрятанную Петей клику.
187. Задача о наибольшем общем подграфе. Рассмотрим два графа, выбранных из распределения $G(n, 1/2)$. Найдем их общий индуцированный подграф размера $k$: выберем в каждом графе по $k$ вершин, оставим все ребра между ними, получившиеся графы должны быть изоморфны. Докажите, что наибольший общий подграф двух графов а.п.н. имеет размер не больше $4 \log_2 n$.
188. Напишите генератор графов $G(n, p)$ на вашем любимом языке программирования и примените в этом и последующих заданиях. Проведите численные эксперименты с генератором для различных значений $n$ и $p$, соотнесите результаты с теорией, которую вы узнали на лекциях. В качестве ответа на задание продемонстрируйте графики зависимости вероятности от $p$, другие результаты численных экспериментов, можно также запускать программу с демонстрацией результатов запуска на проекторе. Проанализируйте появление треугольников для $p=\frac cn$ в зависимости от константы $c$.
189. Продемонстрируйте появление свойства ""диаметр 2"" при $p=\sqrt{2 \ln n/n}$.
190. Проанализируйте исчезновение изолированных вершин и появление связности на одном графике.
191. Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.
192. Постройте матроид с 5 элементами и 12 базами.
193. Матроид с выброшенным элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются независимые множества исходного матроида, которые не содержали $x$. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A | A \in I, x \notin A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setminus x$ является матроидом.
194. Матроид, стянутый по элементу. Пусть $M$ - матроид. Обозначим как $M/x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются независимые множества исходного матроида, которые ранее содержали $x$, после удаления из них этого элемента. Формально, если $M = \langle X, I\rangle$, то $M/x = \langle X \setminus x, \{A \setminus x | A \in I, x \in A\}\rangle$. Докажите, что для любых $M$ и $x$, таких что $\{x\}\in I$ получившаяся конструкция $M/x$ является матроидом.
195. Докажите, что если $x \ne y$, то $M\setminus x/y=M/y\setminus x$
196. Урезанный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M|_k$ следующую констркуцию: $M|_k = \langle X, \{A | A \in I, |A| \le k \}\rangle$. Докажите, что $M|_k$ является матроидом.
197. Прямая сумма матроидов. Пусть $X$ и $Y$ - непересекающиеся множества, $M_1$ - матроид с носителем $X$ и $M_2$ - матроид с носителем $Y$. Построим новый матроид, назовем носителем объединение $X \cup Y$, независимыми объявим множества, которые являются объединением независимого из $M_1$ и независимого из $M_2$. Докажите, что прямая сумма матроидов является матридом.
198. Представьте разноцветный матроид в виде прямой суммы универсальных матроидов.
199. Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
200. Являются ли паросочетания в полном графе семейством независимых множеств некоторого матроида?
201. Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
202. Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксиомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
203. Пусть $M$ - предматроид. Как и в матроиде будем называть базой множества максимальное по включению подмножество из $I$. Докажите, что если для каждого множества $A$ все его базы равномощны, то $M$ - матроид.
204. Для каких универсальных матроидов существует изоморфный ему матричный матроид?
205. Проекция матроида. Пусть $M = \langle X, I \rangle$ - матроид, $f : X \to Y$ - произвольная функция. Обратите внимание, что нет необходимости, чтобы $f$ была инъекцией или сюрьекцией. Построим конструкцию $f(M)$ как пару из носителя $Y$ и семейства множеств $f(I) = \{ f(A) \,|\, A \in I\}$. Докажите, что $f(M)$ является матроидом.
206. Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
207. Дайте альтернативное определение параллельных элементов на языке баз.
208. Докажите, что отношение "быть параллельными" является транзитивным.
209. (для 34-35) Как устроено замыкание в графовом матроиде?
210. (для 34-35) Как устроено замыкание в матричном матроиде?
211. Докажите, что если $A$ независимо, то для любого $p \in A$ выполнено $p \not\in \langle A \setminus p\rangle$.
212. Докажите, что если $A \subset B$, то $\langle A \rangle \subset \langle B \rangle$.
213. Докажите, что $\langle \langle A \rangle \rangle = \langle A \rangle$
214. Докажите, что если $q \not\in \langle A \rangle$, $q \in \langle A \cup p\rangle$, то $p \in \langle A \cup q \rangle$
215. Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую конструкцию: $M^* = \langle X, \{A \,|\, \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
216. Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом.
217. Докажите, что двойственный к матричному матроид изоморфен матричному для некоторой матрицы. Как устроена его матрица?
218. В этой и следующих задача граф для графового матроида может содержать кратные ребра. Докажите, что двойственный к графовому матроиду колеса $C_4 + K_1$ изоморфен графовому для некоторого графа
219. Докажите, что двойственный к графовому матроиду графа $K_{2, 3}$ изоморфен графовому для некоторого графа
220. Докажите, что двойственный матроид к графовому на $K_5$ не изоморфен графовому ни для какого графа.
221. Докажите, что двойственный матроид к графовому на $K_{3,3}$ не изоморфен графовому ни для какого графа.
222. Когда двойственный к графовому матроид изоморфен графовому для некоторого графа?
223. Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $X = \{x_1, x_2, \ldots, x_n\}$. Пусть $Y = \left\{x_k \,|\, rank(\{x_1, \ldots, x_{k-1}, x_k\}) > rank(\{x_1, \ldots, x_{k-1}\})\right\}$. Докажите, что $Y$ независимо.
224. Сверхсильная теорема о базах. Докажите, что для любых двух различных баз $A$ и $B$ и элемента $x \in A \setminus B$ найдётся $y \in B \setminus A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
225. Доказать, что $M^{**}=M$
226. Один студент считает, что xor двух циклов обязательно содержит цикл. Доказать или опровергнуть.