Список заданий по ДМ 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$, которые не являются мостами, образуют один простой цикл.
39. Обозначим как $\lambda(G)$ минимальное число ребер, которое нужно удалить в графе, чтобы он потерял связность, $\kappa(G)$ - минимальное число вершин, которое нужно удалить в графе, чтобы он потерял связность (для полного графа полагаем $\kappa(G)=n-1$). Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
40. Докажите. что для любых $1 \le \kappa(G) \le \lambda(G) \le \delta(G)$ существует граф $G$ с такими параметрами.
41. Докажите, что не существует графов с $\kappa(G) = 3$ и 7 ребрами.
42. Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
43. Пусть $G$ - полный двудольный граф, за исключением $K_{2,2}$. Докажите $\lambda(G)=\delta(G)$, почем единственный способ удалить $\lambda(G)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин.
44. Докажите, что если в связном графе любой блок эйлеров, то и весь граф эйлеров.
45. Граф называется произвольно вычерчиваемым из вершины $u$, если следующая процедура всегда приводит к эйлеровому циклу: начиная с вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, по которому ранее не проходили. Докажите, что эйлеров граф является произвольно вычерчиваемым из $u$, если любой его простой цикл содержит $u$.
46. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то $u$ имеет максимальную степень в $G$.
47. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то либо $u$ - единственная точка сочленения в $G$, либо в $G$ нет точек сочленения.
48. Доказать или опровегнуть, что если $G$ содержит порожденный тета-подграф (две вершины, соединенные тремя путями), то $G$ не гамильтонов.
49. Обозначим как $G^3$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 3. Докажите, что если $G$ связен, то $G^3$ гамильтонов.
50. Граф называется произвольно гамильтоновым, если следующая процедура всегда приводит к гамильтонову циклу: начиная с произвольной вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, другой конец которого мы ранее не посещали, либо обратно в вершину $u$, если непосещенных соседей нет. Опишите все произвольно гамильтоновы графы.
51. Теорема "Антихватала". Докажите, что если не выполнено условие теоремы Хватала, то найдется граф с такой степенной последовательностью, не содержащий гамильтонова цикла.
52. Докажите, что если сумма степеней любых двух несмежных вершин графа $G$ не меньше $n+1$, то любые две различные вершины $G$ можно соединить гамильтоновым путем.
53. Докажите, что для любого $k$ существует негамильтонов граф с $\kappa(G)=k$.
54. Обозначим как $G^2$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 2. Докажите, что если $G$ вершинно двусвязен, то $G^2$ гамильтонов.
55. Докажите теорему Гуйя-Ури: если в ориентированном графе у любой вершины как входящая, так и исходящая степень хотя бы $n/2$, то он гамильтонов.
56. Докажите усиленную версию теоремы Редеи-Камеона: в любом сильно связном турнире с $n$ вершинами есть простой цикл любой длины от $3$ до $n$.
57. Докажите, что различные деревья имеют различные коды Прюфера.
58. Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
59. Докажите, что если $v$ — точка сочленения в $G$, то $v$ не точка сочленения в $\overline G$.
60. Опишите все деревья с диаметром 2.
61. Опишите все деревья с диаметром 3.
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^2$ эйлеров.
68. Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $G_E^2$ эйлеров, то и $G_E^3$ эйлеров.
69. Постройте минимальный по числу вершин реберный граф, в котором нет гамильтонова цикла.
70. Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий хотя бы одну вершину, инцидентную каждому ребру графа $G$.
71. Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.
72. Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?
73. Докажите или опровергните, что если в связном графе любой максимальный по включению простой путь (путь, к которому нельзя добавить ребро в начало или в конец) является диаметром, то такой граф является деревом.
74. Опишите дерево с кодом Прюфера $(i, i,\ldots , i)$.
75. Опишите деревья, в коде Прюфера которых нет одинаковых чисел.
76. Зафиксируем дерево $T$. Рассмотрим функцию от вершины $x$: $d(x) = \sum_v dist(x, v)$, где $dist(x, v)$ - расстояние между вершинами $x$ и $v$ в ребрах. Пусть $y$ и $z$ - различные соседи вершины $x$. Докажите, что $2d(x) < d(y) + d(z)$.
77. Центром дерева называется вершина $x$, для которой $max_v(dist(x, v))$ минимален. Докажите, что у дерева 1 или 2 центра, и любой центр дерева лежит на его любом диаметре.
78. Барицентром дерева называется вершина $x$, для которой $\sum_v(dist(x, v))$ минимальная. Докажите, что у дерева 1 или 2 барицентра.
79. Докажите, что для любого $k$ существует дерево, для которого расстояние между центром и барицентром не меньше $k$.
80. Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев.
81. Приведите пример графа с двумя непересекающимися остовными деревьями.
82. Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами?
83. Пусть связный граф $G$ имеет диаметр $d$. Докажите или опровергните, что у $G$ есть остовное дерево с диаметром $d$.
84. Рассмотрим множество остовных деревьев связного графа $G$. Построим граф $S_G$, вершинами которого являются остовные деревья $G$, а две вершины $T_1$ и $T_2$ соединены ребром, если дерево $T_2$ можно получить из $T_1$ удалением одного ребра и добавлением другого. Докажите, что $S_G$ является связным.
85. Докажите, что две вершины $T_1$ и $T_2$ в $S_G$ соединены ребром тогда и только тогда, когда их объединение содержит ровно один простой цикл.
86. Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$.
87. Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$.
88. Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$.
89. Графы $G_1$, содержащий $n_1$ вершин и $m_1$ ребер, и $G_2$, содержащий $n_2$ вершин и $m_2$ ребер, гомеоморфны. Докажите, что $n_1+m_2 = n_2+m_1$.
90. Докажите, что планарный эйлеров граф содержит эйлеров цикл, не имеющий самопересечений.
91. Пусть планарный граф $G$ без петель и параллельных ребер содержит $n$ вершин. Какое максимальное число ребер он может содержать?
92. Приведите пример духсвязного планарного графа, который не является гамильтоновым.
93. Докажите, что планарный четырехсвязный граф гамильтонов.
94. Пусть $G$ - планарный граф, в котором каждый треугольник ограничивает область, не содержащую ребер, причем добавление любого ребра нарушает это свойство. Докажите, что $G$ гамильтонов.
95. Докажите или опровергните, что циклы вокруг конечных граней образуют базис циклического пространства планарного графа.
96. Докажите, что любой трехсвязный планарный граф имеет остов, у которого наибольшая степень равна 3.
97. Докажите, что все колеса самодвойственны.
98. Найдите максимальное $k$, что граф $K_k$ можно уложить на торе.
99. Найдите максимальное $k$, что граф $K_k$ можно уложить на сфере с двумя ручками.
100. Докажите, что для любого $m$ существует $k$, такое что граф с $K_k$ нельзя уложить на сфере с $m$ ручками.
101. Посчитать хроматический многочлен цикла $C_n$
102. Посчитать хроматический многочлен колеса $C_n + K_1$.
103. Посчитать хроматический многочлен полного двудольного графа $K_{n,m}$.
104. Докажите, что хроматический многочлен дерева равен $t(t-1)^{n - 1}$.
105. Докажите, что если хроматический многочлен графа равен $t(t-1)^{n - 1}$, то граф является деревом.
106. Приведите пример двух графов, которые не являются деревьями, не являются изоморфными и имеют одинаковые хроматические многочлены.
107. Докажите, что если длина максимального простого нечетного цикла в $G$ есть $k$, то $\chi(G)\le k + 1$.
108. Если степени вершин графа $G$ равны $d_1 \ge d_2 \ge \ldots \ge d_n$, то $\chi(G)\le \max\min\{i, d_i+1\}$.
109. Докажите или опровергните, что если граф $G$ с $n$ вершинами содержит гамильтонов цикл, причем ему принадлежат не все ребра графа, то (а) $\chi(G) \le 1 + n/2$ (б) $\chi(G) \ge 1 + n/2$ .
110. Хроматическое число конъюнкции $G_1\wedge G_2$ графов $G_1$ и $G_2$ двух графов не превосходит хроматических чисел этих графов.
111. Докажите, что $K_{n+1}$ является единственным регулярным графом степени $n$, который имеет хроматическое число $n+1$.
112. Рассмотрим связный граф $G$, не являющийся простым циклом нечетной длины, все простые циклы которого нечетный. Обозначим как $\chi'(G)$ минимальное число цветов, в которое можно раскрасить ребра граф $G$, чтобы ни в какую вершину не входило ребер одного цвета. Докажите, что $\chi'(G)=\Delta(G)$.
113. Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
114. Доказать формулу Уитни: пусть $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$ рёбер.
115. Вершинным покрытием называется множество вершин, такое что у каждого ребра хотя один конец лежит в этом множестве. Докажите, что $A$ является вершинным покрытием тогда и только тогда, когда $V\setminus A$ является независимым множеством.
116. Доказать или опровернгнуть: любое вершинное покрытие содержит как подмножество минимальное по мощности вершинное покрытие.
117. Доказать или опровергнуть: если в $G$ содержится замкнутый путь, содержащий вершинное покрытие, то его реберный граф $E_G$ гамильтонов.
118. Докажите, что $\alpha(G) \ge \frac{n}{1+\Delta(G)}$.
119. Докажите, что $\alpha(G) \ge \sum (1 + \deg u)^{-1}$.
120. Как может поменяться $\alpha(G)$ при удалении ребра? Удалении вершины? Добавлении ребра?
121. Верно ли, что для двудольного графа значение $\alpha(G)$ равно размеру максимальной доли?
122. Докажите, что $G$ двудольный тогда и только тогда, когда для любого $H$ - подграфа $G$ выполнено $\alpha(H) \ge |VH|/2$ ($VH$ - множество вершин графа $H$).
123. Докажите, что если в дереве расстояние между двумя любыми листьями четно, то в нем существует единственное максимальное по включению множество. Верно ли обратное?
124. Зафиксируем $n$ и $k$. Рассмотрим граф, удовлетворяющий следующим условиям: (1) граф $G$ содержит $n$ вершин; (2) $\alpha(G) \le k$. Среди таких графов рассмотрим граф с минимальным числом ребер. Этот граф называется граф Турана. Докажите, что в графе Турана любые две смежные вершины имеют равную степень.
125. Степень любых двух несмежных вершин в графе Турана отличается не более чем на $1$.
126. Оцените, сколько ребер в графе Турана.
127. Граф называется $\alpha$-критическим, если удаление любого ребра увеличивает $\alpha(G)$. Приведите пример $\alpha$-критического и не $\alpha$-критического графа.
128. Докажите, что в любом дереве, кроме $K_2$ существует минимальное по числу вершин вершинное покрытие, включающее все вершины, соседние с листьями.
129. Доминирующим множеством в графе называется множество вершин, такое что каждая вершина либо входит в это множество, либо имеет соседа в этом множестве. Докажите, что независимое множество вершин является максимальным по включению если и только если оно является доминирующим.
130. Обозначим размер минимального доминирующего множества в графе как $\gamma(G)$. Как связаны $\alpha(G)$ и $\gamma(G)$?
131. Докажите, что если в графе $G$ нет изолированных вершин, и $A$ - минимальное по включению доминирующее множество в $G$, то существует $B$, не имеющее общих вершин с $A$, также являющееся минимальным по включению доминирующим множеством в $G$.
132. Обозначим размер минимального по мощности покрывающего множества в графе как $\beta(G)$. Как связаны $\gamma(G)$ и $\beta(G)$?

</wikitex>