Редактирование: Список заданий по ДМ 2к 2019 осень
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 194: | Строка 194: | ||
# Докажите, что если $A \subset B$, то $\langle A \rangle \subset \langle B \rangle$. | # Докажите, что если $A \subset B$, то $\langle A \rangle \subset \langle B \rangle$. | ||
# Докажите, что $\langle \langle A \rangle \rangle = \langle A \rangle$ | # Докажите, что $\langle \langle A \rangle \rangle = \langle A \rangle$ | ||
− | # Докажите, что если $ | + | # Докажите, что если $p \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^*$ является матроидом. | # Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую конструкцию: $M^* = \langle X, \{A \,|\, \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом. | ||
# Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом. | # Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом. | ||
# Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица? | # Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица? | ||
− | # Докажите, что двойственный матроид к $K_5$ не является графовым | + | # Докажите, что двойственный матроид к $K_5$ не является графовым. |
− | # Докажите, что двойственный матроид к $K_{3,3}$ не является графовым | + | # Докажите, что двойственный матроид к $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$ независимо. | # Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $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 \subset B$ найдётся $y \in B \subset A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами. | # Сверхсильная теорема о базах. Докажите, что для любых двух различных баз $A$ и $B$ и элемента $x \in A \subset B$ найдётся $y \in B \subset A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами. |