Изменения
Нет описания правки
# Докажите лемму о паросочетании в графе замен (формулировка тут: [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B2_%D0%B3%D1%80%D0%B0%D1%84%D0%B5_%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD], доказательство неправильное - неверный индукционный переход)
# Рассмотрим два матроида $M_1$ и $M_2$. Как связаны максимальное независимое множество пересечения $M_1 \cap M_2$ и база $M_1 \cup M_2^*$? ($M_2^*$ - матроид, двойственный $M_2$)
# Докажите теорему Радо: пусть $M$ - матроид с ранговой функцией $r$, $X = X_1 \cup X_2 \cup ...\cup X_k$, причем все $X_i$ попарно не пересекаются. Будем называть независимой системой представителей независимое множество $A$, такое что $|A \cap X_i| \le 1$. Пусть $A_{max}$ - максимальная по мощности независимая система представителей. Тогда $|A_{max}|=\min_{Z\subset \{1,..,k\}}(r(\cup_{i\in Z} X_i)+k-|Z|)$.
</wikitex>
