Изменения
Нет описания правки
# Двойственный матроид. Пусть $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|_k$ следующую констркуцию: $M|_k = \langle X, \{A | A \in I, |A| \le k \}\rangle$. Докажите, что $M|_k$ является матроидом.
# Докажите теорему об аксиоматизации циклами.
# Докажите теорему о рангах.
# Докажите теорему об аксиоматизации рангами.
# Докажите теорему о замыкании.
# Докажите теорему об аксиоматизации замыканиями.
# Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксимомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
# Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup 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$ независимо.
# Какие универсальные матроиды являются матричными?
# Докажите, что матроид Вамоса не является представимым ни над каким полем.
# Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
# Когда двойственный к графовому матроид является графовым?
</wikitex>
