1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Докажите, что пересечение двух максимальных по включению барьеров также является барьером.
# Пусть $x\in A(G)\cup C(G)$, $G'=G\setminus x$, $B'$ - барьер графа $G'$. Докажите, что $B=B'\cup x$ - барьер графа $G$. Следствие: любая вершина из $A(G) \cup C(G)$ входит в барьер графа $G$.
# Пусть $B$ - барьер графа $G$, тогда $B\cap D(G)$ пусто и все нечетные компоненты $D(G)$ являются подмножествами нечетных компонент связности графа $G\setminus B$ являются подмножествами $D(G)$.
# Пусть $B$ - барьер графа $G$, причем $x \in B$. Тогда $B' = B \setminus x$ - барьер графа $G' = G \setminus x$.
# Докажите, что пересечение всех максимальных по включению барьеров $G$ равно $A(G)$.
# Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
# Докажите, что если $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
# Матроид с выкинутым элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Множества, не содержавшие $x$, остаются независимыми. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A | A \in I, x \not\in A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setminus x$ является матроидом.
# Матроид, стянутый по элементу. Пусть $M$ - матроид. Обозначим как $M/x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются множества, которые ранее содержали $x$, после удаления из них этого элемента. Формально, если $M = \langle X, I\rangle$, то $M/x = \langle X \setminus x, \{A \setminus x | A \in I, x \in A\}\rangle$. Докажите, что для любых $M$ и $x$, таких что $\{x\}\in I$ получившаяся конструкция $M/x$ является матроидом.
# Разноцветные множества. Пусть $X$ - множество элементов, каждый из которых раскрашен в некоторый цвет. Будем называть независимыми множества, в которых все элементы разного цвета. Докажите, что эта конструкция является матроидом. Используйте определение матроида.
# Представьте конструкцию из предыдущего примера в виде прямой суммы универсальных матроидов.
# Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
# Является ли венгерский алгоритм вариантом алгоритма Радо-Эдмондса?
# Образуют ли паросочетания в полном графе семейство независимых множеств некоторого матроида?
# Рассмотрим кратчайшие пути из $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^*$ является матроидом.
# Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом?
# Будем называть два элемента $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>
