Список заданий по ДМ 2к 2023 осень - История изменений

Admin в 06:34, 2 декабря 2023

2023-12-02T06:34:36Z

Admin в 17:35, 27 ноября 2023

2023-11-27T17:35:49Z

Admin в 17:16, 25 ноября 2023

2023-11-25T17:16:05Z

Admin в 09:32, 22 ноября 2023

2023-11-22T09:32:59Z

Admin в 13:36, 8 ноября 2023

2023-11-08T13:36:24Z

Admin в 13:35, 8 ноября 2023

2023-11-08T13:35:40Z

Admin в 21:33, 7 ноября 2023

2023-11-07T21:33:28Z

Admin в 12:18, 1 ноября 2023

2023-11-01T12:18:22Z

Admin в 12:16, 1 ноября 2023

2023-11-01T12:16:49Z

Admin в 12:16, 1 ноября 2023

2023-11-01T12:16:21Z

← Предыдущая		Версия 06:34, 2 декабря 2023
Строка 199:		Строка 199:
	# Дайте альтернативное определение параллельных элементов на языке баз.		# Дайте альтернативное определение параллельных элементов на языке баз.
	# Докажите, что отношение ""быть параллельными"" является транзитивным.		# Докажите, что отношение ""быть параллельными"" является транзитивным.
		+	# Как устроено замыкание в графовом матроиде?
		+	# Как устроено замыкание в матричном матроиде?
		+	# Докажите, что если $A$ независимо, то для любого $p \in A$ выполнено $p \not\in \langle A \setminus p\rangle$.
		+	# Докажите, что если $A \subset B$, то $\langle A \rangle \subset \langle B \rangle$.
		+	# Докажите, что $\langle \langle A \rangle \rangle = \langle A \rangle$
		+	# Докажите, что если $q \not\in \langle A \rangle$, $q \in \langle A \cup p\rangle$, то $p \in \langle A \cup q \rangle$
		+	# Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^$ следующую конструкцию: $M^ = \langle X, \{A \,\|\, \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
		+	# Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом.
		+	# Докажите, что двойственный к матричному матроид изоморфен матричному для некоторой матрицы. Как устроена его матрица?
		+	# В этой и следующих задача граф для графового матроида может содержать кратные ребра. Докажите, что двойственный к графовому матроиду колеса $C_4 + K_1$ изоморфен графовому для некоторого графа
		+	# Докажите, что двойственный к графовому матроиду графа $K_{2, 3}$ изоморфен графовому для некоторого графа
		+	# Докажите, что двойственный матроид к графовому на $K_5$ не изоморфен графовому ни для какого графа.
		+	# Докажите, что двойственный матроид к графовому на $K_{3,3}$ не изоморфен графовому ни для какого графа.
		+	# Когда двойственный к графовому матроид изоморфен графовому для некоторого графа?
		+	# Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $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$ независимо.
		+	# Сверхсильная теорема о базах. Докажите, что для любых двух различных баз $A$ и $B$ и элемента $x \in A \setminus B$ найдётся $y \in B \setminus A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
		+	# Доказать, что $M^{**}=M$
		+	# Один студент считает, что xor двух циклов обязательно содержит цикл. Доказать или опровергнуть.

@@ Строка 183: / Строка 183: @@
 # Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.
 # Постройте матроид с 5 элементами и 12 базами.
-# Матроид с выброшенным элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются независимые множества исходного матроида, которые не содержали $x$. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A \setminus x | A \in I, x \not\in A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setmunis x$ является матроидом.
+# Матроид с выброшенным элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются независимые множества исходного матроида, которые не содержали $x$. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A \setminus x | A \in I, x \not\in A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setminus x$ является матроидом.
 # Матроид, стянутый по элементу. Пусть $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$ является матроидом.
 # Докажите, что если $x \ne y$, то $M\setminus x/y=M/y\setminus x$

← Предыдущая		Версия 17:16, 25 ноября 2023
Строка 181:		Строка 181:
	# Предложите полиномиальный алгоритм поиска $\alpha(G)$ для хордального графа $G$.		# Предложите полиномиальный алгоритм поиска $\alpha(G)$ для хордального графа $G$.
	# Предложите полиномиальный алгоритм поиска $\chi(G)$ для хордального графа $G$.		# Предложите полиномиальный алгоритм поиска $\chi(G)$ для хордального графа $G$.
		+	# Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.
		+	# Постройте матроид с 5 элементами и 12 базами.
		+	# Матроид с выброшенным элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются независимые множества исходного матроида, которые не содержали $x$. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A \setminus x \| A \in I, x \not\in A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setmunis x$ является матроидом.
		+	# Матроид, стянутый по элементу. Пусть $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$ является матроидом.
		+	# Докажите, что если $x \ne y$, то $M\setminus x/y=M/y\setminus x$
		+	# Урезанный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M\|_k$ следующую констркуцию: $M\|_k = \langle X, \{A \| A \in I, \|A\| \le k \}\rangle$. Докажите, что $M\|_k$ является матроидом.
		+	# Прямая сумма матроидов. Пусть $X$ и $Y$ - непересекающиеся множества, $M_1$ - матроид с носителем $X$ и $M_2$ - матроид с носителем $Y$. Построим новый матроид, назовем носителем объединение $X \cup Y$, независимыми объявим множества, которые являются объединением независимого из $M_1$ и независимого из $M_2$. Докажите, что прямая сумма матроидов является матридом.
		+	# Представьте разноцветный матроид в виде прямой суммы универсальных матроидов.
		+	# Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
		+	# Являются ли паросочетания в полном графе семейством независимых множеств некоторого матроида?
		+	# Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
		+	# Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксиомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
		+	# Пусть $M$ - предматроид. Как и в матроиде будем называть базой множества максимальное по включению подмножество из $I$. Докажите, что если для каждого множества $A$ все его базы равномощны, то $M$ - матроид.
		+	# Для каких универсальных матроидов существует изоморфный ему матричный матроид?
		+	# Проекция матроида. Пусть $M = \langle X, I \rangle$ - матроид, $f : X \to Y$ - произвольная функция. Обратите внимание, что нет необходимости, чтобы $f$ была инъекцией или сюрьекцией. Построим конструкцию $f(M)$ как пару из носителя $Y$ и семейства множеств $f(I) = \{ f(A) \,\|\, A \in I\}$. Докажите, что $f(M)$ является матроидом.
		+	# Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
		+	# Дайте альтернативное определение параллельных элементов на языке баз.
		+	# Докажите, что отношение ""быть параллельными"" является транзитивным.

@@ Строка 170: / Строка 170: @@
 # Приведите пример хордального графа, который не является интервальным
 # Докажите, что хордальный граф является интервальным тогда и только тогда, когда его дополнение является графом сравнений (теорема Гилмора-Хоффмана)
-# Докажите, что граф $G$ является совершенным тогда и только тогда, когда $|H| = \alpha(H)\omega(H)$ для любого $H$ - индуцированного подграфа $G$ (теорема Ловаса)
+# Докажите, что граф $G$ является совершенным тогда и только тогда, когда $|H| \le \alpha(H)\omega(H)$ для любого $H$ - индуцированного подграфа $G$ (теорема Ловаса)
 # Докажите, что если $G$ является реберным графом, то $\chi(G) \in \{\omega(G), \omega(G)+1\}$.
 # Опишите графы, у которых реберный граф является совершенным

@@ Строка 180: / Строка 180: @@
 # Предложите полиномиальный алгоритм проверки, что граф является хордальным.
 # Предложите полиномиальный алгоритм поиска $\alpha(G)$ для хордального графа $G$.
-# Предложите полиномиальный алгоритм поиска $\chiG)$ для хордального графа $G$.
+# Предложите полиномиальный алгоритм поиска $\chi(G)$ для хордального графа $G$.

← Предыдущая		Версия 13:35, 8 ноября 2023
Строка 164:		Строка 164:
	# Найдите $R(P_4, P_4)$		# Найдите $R(P_4, P_4)$
	# Завершите доказательство теоремы Хватала, показав, что $R(T_m, K_n) \ge (n-1)(m-1)+1$		# Завершите доказательство теоремы Хватала, показав, что $R(T_m, K_n) \ge (n-1)(m-1)+1$
		+	# Покажите, что добавление ребра может сделать совершенный граф несовершенным
		+	# Покажите, что удалине ребра может сделать совершенный граф несовершенным
		+	# Докажите, что любой интервальный граф является хордальным
		+	# Докажите, что дополнение любого интервального графа является графом сравнений
		+	# Приведите пример хордального графа, который не является интервальным
		+	# Докажите, что хордальный граф является интервальным тогда и только тогда, когда его дополнение является графом сравнений (теорема Гилмора-Хоффмана)
		+	# Докажите, что граф $G$ является совершенным тогда и только тогда, когда $\|H\| = \alpha(H)\omega(H)$ для любого $H$ - индуцированного подграфа $G$ (теорема Ловаса)
		+	# Докажите, что если $G$ является реберным графом, то $\chi(G) \in \{\omega(G), \omega(G)+1\}$.
		+	# Опишите графы, у которых реберный граф является совершенным
		+	# Докажите, что граф $G$ является совершенным тогда и только тогда, когда его любой непустой индуцированный подграф $H$ содержит независимое множество $A$, такое что $\omega(H \setminus A) < \omega(H)$.
		+	# Рассмотрим граф $G$, такой что для любого индуцированного подграфа $H$ любая максимальная клика и любое максимальное независимое множество имеют общую вершину. Докажите, что $G$ совершенный.
		+	# Докажите, что $G$ обладает свойством из предыдущего задания тогда и только тогда, когда $G$ не содержит индуцированного пути из трех вершин (любые три вершины соединены либо 0, либо 1, либо 3 ребрами).
		+	# Рассмотрим совершенный граф $G$. Докажите, что можно покрыть все вершины графа независимыми множествами (обозначим семейство этих независимых множеств $\mathbb{I}$), а также покрыть все вершины графа кликами (обозначим семейство этих клик как $\mathbb{J}$, что для любых $A \in \mathbb{I}$ и $B \in \mathbb{J}$ выполнено $A \cap B \ne \emptyset$.
		+	# Рассмотрим совершенный граф $G$. Заметим каждую его вершину $x$ на произвольный совершенный граф $G_x$ (вершины графов $G_x$ и $G_y$ соединены друг с другом, если было ребро $xy$). Докажите, что получившийся граф является совершенным.
		+	# Предложите полиномиальный алгоритм проверки, что граф является хордальным.
		+	# Предложите полиномиальный алгоритм поиска $\alpha(G)$ для хордального графа $G$.
		+	# Предложите полиномиальный алгоритм поиска $\chiG)$ для хордального графа $G$.

@@ Строка 154: / Строка 154: @@
 # Докажите, что из 5 точек на плоскости, никакие три из которых не лежат на одной прямой, можно выбрать 4, являющихся вершинами выпуклого четырехугольника.
 # Докажите, что для любого $n$ найдется $N$, такое что из любых $N$ точек, никакие 3 из которых не лежат на одной прямой, можно выбрать вершины выпуклого $n$-угольника.
-# Докажите, что для любого $n$ найдется такое простое $p$, что существуют натуральные числа $x$, $y$ и $z$, что $x^n+y^n=z^n \pmod p$.
+# Докажите, что для любого $n$ найдется такое простое $p$, что существуют натуральные числа $x$, $y$ и $z$, не кратные $p$, что $x^n+y^n=z^n \pmod p$.
 # Докажите усиление теоремы Эрдёша: $R(k, k) \ge \frac{2^{k/2}\cdot k}{e\sqrt{2}}$
 # Докажите, что для любого достаточно большого $s$ выполнено $R(k, k) \ge s - {s \choose k}\cdot 2^{1-{k \choose 2}}$

@@ Строка 156: / Строка 156: @@
 # Докажите, что для любого $n$ найдется такое простое $p$, что существуют натуральные числа $x$, $y$ и $z$, что $x^n+y^n=z^n \pmod p$.
 # Докажите усиление теоремы Эрдёша: $R(k, k) \ge \frac{2^{k/2}\cdot k}{e\sqrt{2}}
-# Докажите, что для любого достаточно большого $s$ выполнено $R(k, k) \ge s - {s \choose k}\cdot 2^{1-{k \сhoose 2}}$
+# Докажите, что для любого достаточно большого $s$ выполнено $R(k, k) \ge s - {s \choose k}\cdot 2^{1-{k \choose 2}}$
 # Докажите, что в любой перестановке $n$ элементов найдется возрастающая последовательность из $\sqrt{n}$ элементов или убывающая последовательнтсть из $\sqrt{n}$ элементов.
 # Теорема Ван дер Вардена. Докажите, что для любых $n$ и $k$ найдется такое $W(n, k)$, что если числа от $1$ до $W(n, k)$ покрасить в $k$ цветов, то найдется арифметическая прогрессия длины $n$, покрашенная в один цвет.

← Предыдущая		Версия 12:16, 1 ноября 2023
Строка 147:		Строка 147:
	# Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.		# Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
	# Докажите, что если связный граф $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).		# Докажите, что если связный граф $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
		+	# Найдите $R(3, 4)$
		+	# Докажите, что $R(n, 3) \le (n^2+3)/2$
		+	# Найдите $R(3, 3, 3)$
		+	# На плоскости даны 6 точек, никакие 3 из которых не лежат на одной прямой и все попарные расстояния между которыми различны. Рассмотрим все треугольники с вершинами в этих точках. Докажите, что найдется отрезок, который в одном из этих треугольников является наибольшей стороной, а в другом - наименьшей.
		+	# Обобщение теоремы Шура. Докажите, что для любого натурального $k$ найдется такое $n$, что в любой раскраске чисел от 1 до $n$ в $k$ цветов найдутся различные $x$ и $y$, такие что $x$, $y$ и $x+y$ раскрашены в один цвет.
		+	# Докажите, что из 5 точек на плоскости, никакие три из которых не лежат на одной прямой, можно выбрать 4, являющихся вершинами выпуклого четырехугольника.
		+	# Докажите, что для любого $n$ найдется $N$, такое что из любых $N$ точек, никакие 3 из которых не лежат на одной прямой, можно выбрать вершины выпуклого $n$-угольника.
		+	# Докажите, что для любого $n$ найдется такое простое $p$, что существуют натуральные числа $x$, $y$ и $z$, что $x^n+y^n=z^n \pmod p$.
		+	# Докажите усиление теоремы Эрдёша: $R(k, k) \ge \frac{2^{k/2}\cdot k}{e\sqrt{2}}
		+	# Докажите, что для любого достаточно большого $s$ выполнено $R(k, k) \ge s - {s \choose k}\cdot 2^{1-{k \сhoose 2}}$
		+	# Докажите, что в любой перестановке $n$ элементов найдется возрастающая последовательность из $\sqrt{n}$ элементов или убывающая последовательнтсть из $\sqrt{n}$ элементов.
		+	# Теорема Ван дер Вардена. Докажите, что для любых $n$ и $k$ найдется такое $W(n, k)$, что если числа от $1$ до $W(n, k)$ покрасить в $k$ цветов, то найдется арифметическая прогрессия длины $n$, покрашенная в один цвет.
		+	# Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что найдутся четыре вершины прямоугольника со сторонами, параллельными осям координат, которые покрашены в один цвет.
		+	# Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что для любых $k$ и $l$ найдутся $k$ строк и $l$ столбцов, что все $kl$ их клеток пересечения покрашены в один и тот же цвет.
		+	# $P_k$ - путь длины $k-1$ (содержащий $k$ вершин и $k-1$ ребро). Найдите $R(P_3, P_3)$.
		+	# Найдите $R(P_4, P_4)$
		+	# Завершите доказательство теоремы Хватала, показав, что $R(T_m, K_n) \ge (n-1)(m-1)+1$