Изменения

Перейти к: навигация, поиск

Список заданий по ДМ 2к 2019 осень

1 байт добавлено, 14:53, 10 декабря 2019
Нет описания правки
# Докажите, что двойственный матроид к $K_5$ не является графовым ни для какого графа.
# Докажите, что двойственный матроид к $K_{3,3}$ не является графовым ни для какого графа.
# Когда двойственный к графовому матроид является графовым (возможно , для графа, не совпадающего с изначальным)?
# Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $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$ независимо.
# Сверхсильная теорема о базах. Докажите, что для любых двух различных баз $A$ и $B$ и элемента $x \in A \subset B$ найдётся $y \in B \subset A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
Анонимный участник

Навигация