Изменения
Нет описания правки
# Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
# Урезанный матроид. Пусть $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$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
# Пусть $M$ - предматроид. Как и в матроиде будем называть базой множества максимальное подмножество из $I$. Докажите, что если для каждого множества $A$ все его базы равномощны, то $M$ - матроид.
# Для каких универсальных матроидов существует изоморфный ему матричный матроид?
# Замыканием множества $\langle A \rangle$ называется множество $\langle A \rangle = A \cup \{p | r(A \cup p) = r(A)$. Как устроено замыкание в графовом матроиде?
# Как устроено замыкание в матричном матроиде?
# Докажите теорему о замыканиях: (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$
# Докажите теорему об аксиоматизации замыканиями.
# Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую констркуцию: $M^* = \langle X, \{A | \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
