207
правок
Изменения
Нет описания правки
# Дайте альтернативное определение параллельных элементов на языке баз.
# Докажите, что отношение ""быть параллельными"" является транзитивным.
# Замыкание для множества $A$ в матроиде определено так: $\langle A \rangle = \{b | r(A \cup b) = r(A)$ Как устроено замыкание в графовом матроиде?
# Как устроено замыкание в матричном матроиде?
# Докажите, что если $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 двух циклов обязательно содержит цикл. Доказать или опровергнуть.
