Список заданий по ДМ 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$. Рассмотрим граф, удовлетворяющpий следующим условиям: (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)$?
133. $k$-факторизацией графа называется разбиение множество ребер графа на его $k$-факторы. Докажите, что $K_4$ имеет единственную 1-факторизацию.
134. Найдите число $1$-факторизаций графа $K_6$.
135. Найдите число $1$-факторизаций графа $K_{3,3}$.
136. Найдите число $1$-факторов графа $K_{2n}$.
137. Докажите, что граф $K_{6n-2}$ имеет 3-факторизацию.
138. Докажите, что граф $K_{4n+1}$ имеет 4-факторизацию.
139. Докажите, что граф $K_9$ представим в виде объединения 4 гамильтоновых циклов.
140. Пусть $G$ - связный кубический граф, в котором не более двух мостов. Тогда в $G$ существует совершенное паросочетание.
141. Приведите пример связного кубического графа, содержащего три моста, в котором нет совершенного паросочетания.
142. Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Пусть $G'$ получен из $G$ удалением не более чем $k - 1$ ребер. Тогда $G'$ содержит совершенное паросочетание. Указание: используйте теорему Татта.
143. Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Тогда для любого ребра $uv$ существует совершенное паросочетание, содержащее $uv$.
144. Докажите, что если $G$ - регулярный граф четной степени, то у него есть 2-фактор.
145. Пусть $r<k$ и хотя бы одно из них нечетно. Докажите, что существует $G$ - регулярный граф степени $k$, у которого нет $r$-фактора.
146. Докажите, что у фактор-критического графа единственное множества Татта - пустое.
147. Множество $S\subset V$, для которого $odd(G\setminus S)-|S|=def(G)$, называется барьером. $A(G)$ является барьером графа. Приведите пример графа, в котором $A(G)$ не является максимальным по включению барьером.
148. Приведите пример графа, в котором $A(G)$ не является минимальным по включению барьером.
149. Докажите, что пересечение двух максимальных по включению барьеров также является барьером.
150. Пусть $x\in A(G)\cup C(G)$, $G'=G\setminus x$, $B'$ - барьер графа $G'$. Докажите, что $B=B'\cup x$ - барьер графа $G$. Следствие: любая вершина из $A(G) \cup C(G)$ входит в барьер графа $G$.
151. Пусть $B$ - барьер графа $G$, тогда $B\cap D(G)$ пусто и все компоненты $D(G)$ являются подмножествами нечетных компонент связности графа $G\setminus B$.
152. Пусть $B$ - барьер графа $G$, причем $x \in B$. Тогда $B' = B \setminus x$ - барьер графа $G' = G \setminus x$.
153. Докажите, что пересечение всех максимальных по включению барьеров $G$ равно $A(G)$.
154. Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
155. Докажите, что если $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
156. Матроид с выкинутым элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Множества, не содержавшие $x$, остаются независимыми. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A | A \in I, x \not\in A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setminus x$ является матроидом.
157. Матроид, стянутый по элементу. Пусть $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$ является матроидом.
158. Разноцветные множества. Пусть $X$ - множество элементов, каждый из которых раскрашен в некоторый цвет. Будем называть независимыми множества, в которых все элементы разного цвета. Докажите, что эта конструкция является матроидом. Используйте определение матроида.
159. Представьте конструкцию из предыдущего примера в виде прямой суммы универсальных матроидов.
160. Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
161. Является ли венгерский алгоритм вариантом алгоритма Радо-Эдмондса?
162. Образуют ли паросочетания в полном графе семейство независимых множеств некоторого матроида?
163. Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
164. Урезанный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M|_k$ следующую констркуцию: $M|_k = \langle X, \{A | A \in I, |A| \le k \}\rangle$. Докажите, что $M|_k$ является матроидом.
165. Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксиомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
166. Пусть $M$ - предматроид. Как и в матроиде будем называть базой множества максимальное подмножество из $I$. Докажите, что если для каждого множества $A$ все его базы равномощны, то $M$ - матроид.
167. Для каких универсальных матроидов существует изоморфный ему матричный матроид?
168. Докажите, что матроид Вамоса не является представимым ни над каким полем.
169. Докажите теорему об аксиоматизации циклами.
170. Докажите теорему об аксиоматизации рангами.
171. Замыканием множества $\langle A \rangle$ называется множество $\langle A \rangle = A \cup \{p | r(A \cup p) = r(A)$. Как устроено замыкание в графовом матроиде?
172. Как устроено замыкание в матричном матроиде?
173. Докажите теорему о замыканиях: (1) $A \subset \langle A \rangle$, (2) если $A \subset B$, то $\langle A \rangle \subset \langle B \rangle$, (3) $\langle \langle A \rangle \rangle = \langle A \rangle$, (4) если $p \not\in \langle A \rangle$, $q \in \langle A \cup p\rangle$, то $p \in \langle A \cup q \rangle$
174. Докажите теорему об аксиоматизации замыканиями.
175. Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую констркуцию: $M^* = \langle X, \{A | \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
176. Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом?
177. Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
178. Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $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$ независимо.
179. Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
180. Когда двойственный к графовому матроид является графовым?

</wikitex>