317
правок
Изменения
Нет описания правки
# Доказать, что $M^{**}=M$
# Один студент считает, что xor двух циклов обязательно содержит цикл. Доказать или опровергнуть.
# Докажите, что графовый матроид для графа $K_4$ не изоморфен матроиду паросочетаний ни для какого двудольного графа.
# Листом матроида называют множество, совпадающее со своим замыканием: $A = \langle A\rangle$. Как выглядят листы в графовом матроиде?
# Листом матроида называют множество, совпадающее со своим замыканием: $A = \langle A\rangle$. Как выглядят листы в матричном матроиде?
# Листом матроида называют множество, совпадающее со своим замыканием: $A = \langle A\rangle$. Как выглядят листы в равномером и разноцетном матроидах?
# Докажите, что пересечение листов является листом
# Докажите, что если $S$ - лист, $a \not\in S$, тогда существует единственный лист $T$, такой что $S \cup a \subset T$ и если $S \cup a \subset U \subset T$, то $T = U$.
# Докажите, что весь если носитель входит в некоторое семейство подмножеств $\cal F$, и семейство $\cal F$ удовлетворяет условиям из предыдущих двух заданий, то это семейство образует семейство листов некоторого матроида.
# Рассмотрим множество листов матроида. Введем на нем отношение частичного порядка по включению множеств. Докажите, что у любых двух элементов $X$ и $Y$ есть точная нижняя грань (элемент $Z=X\wedge Y$, такой что $Z \le X$, $Z \le Y$, если $T \le X$, $T \le Y$, то $T \le Z$).
# Докажите, что у любых двух листов $X$ и $Y$ есть точная верхняя грань (элемент $Z=X\vee Y$, такой что $Z \ge X$, $Z \ge Y$, если $T \ge X$, $T \ge Y$, то $T \ge Z$).
# Докажите, что множество листов матроида образует решетку, то есть $X \wedge (X \vee Y) = X$, $X \vee (X \wedge Y) = X$.
# Гиперплоскостью матроида ранга $n$ называют его лист ранга $n-1$. Докажите, что $A$ - гиперплоскость матроида тогда и только тогда, когда его дополнение является коциклом.
# Рассмотрим ориентированный граф, возможно содержащий петли. Будем называть множество вершин $S$ ``разобщенным``, для любой врешины $s$ можно построить бесконечный путь по ребрам графа, начинающийся в $s$, причем эти пути не имеют общих вершин для разных вершин множества $S$. Докажите, что разобщенные множества представляют собой семейство независимых множеств некоторого матроида.
