Изменения
Нет описания правки
# Аксиоматизация рангами, часть 1. Пусть функция $r : 2^X \to \mathbb{Z}^+$ удовлетворяет свойствам: (1) $r(A) \le |A|$, (2) если $A \subset B$, то $r(A) \le r(B)$, (3) для всех множеств $A$ и $B$ выполнено $r(A \cup B) + r(A \cap B) \le r(A) + r(B)$. Назовем псевдонезависимым множество, для которого $r(A) = |A|$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
# Аксиоматизация рангами, часть 2. Докажите, что ранговая функция матроида из предыдущего задания совпадает с функцией $r$.
# Замыканием множества $\langle A \rangle$ называется множество $\langle A \rangle = A \cup \{p \,|\, r(A \cup p) = r(A)\}$. Как устроено замыкание в графовом матроиде?
# Как устроено замыкание в матричном матроиде?
# Докажите, что если $A$ независимо, то для любого $p \in A$ выполнено $p \not\in \langle A \setminus p\rangle$.
# Докажите теорему о замыканиях: (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$
# Аксиоматизация замыканиями часть 1. Пусть функция $span : 2^X \to 2^X$ удовтелворяет свойствам (1)-(4) из предыдущгео предыдущего задания для $\langle \rangle$. Назовем псевдонезависимым множество $A$, если для любого $p \in A$ выполнено $p \not\in span(A \setminus p)$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
# Аксиоматизация замыканиями часть 2. Докажите, что функция замыкания в матроиде из предыдущего задания совпадает с $span$.
# Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую констркуцию: $M^* = \langle X, \{A \,| \, \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
# Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом?
# Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
# Когда двойственный к графовому матроид является графовым?
