Изменения

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

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

11 279 байт добавлено, 10:57, 15 октября 2019
Нет описания правки
# Докажите, что $G$ двудольный тогда и только тогда, когда для любого $H$ - подграфа $G$ выполнено $\alpha(H) \ge |VH|/2$ ($VH$ - множество вершин графа $H$).
# Докажите, что если в дереве расстояние между двумя любыми листьями четно, то в нем существует единственное максимальное по числу вершин независимое множество. Верно ли обратное?
# Зафиксируем $n$ и $k$. Рассмотрим граф, удовлетворяющpий следующим условиям: (1) граф $G$ содержит $n$ вершин; (2) $\alpha(G) \le k$. Среди таких графов рассмотрим граф с минимальным числом ребер. Этот граф называется граф Турана. Докажите, что в графе Турана любые две смежные несмежные вершины имеют равную степень.# Степень любых двух несмежных смежных вершин в графе Турана отличается не более чем на $1$.
# Оцените, сколько ребер в графе Турана.
# Граф называется $\alpha$-критическим, если удаление любого ребра увеличивает $\alpha(G)$. Приведите пример $\alpha$-критического и не $\alpha$-критического графа.
# Докажите, что если $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
# Предложите алгоритм нахождения множества Татта в двудольном графе за $\mathcal{O}(nm)$.
# Матроид, стянутый по элементу. Пусть $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$ и $Y$ - непересекающиеся множества, $M_1$ - матроид с носителем $X$ и $M_2$ - матроид с носителем $Y$. Построим новый матроид, назовем носителем объединение $X \cup Y$, независимыми объявим множества, которые являются объединением независимого из $M_1$ и независимого из $M_2$. Докажите, что прямая сумма матроидов является матридом.
# Представьте разноцветный матроид в виде прямой суммы универсальных матроидов.
# Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
# Является ли венгерский алгоритм вариантом алгоритма Радо-Эдмондса?
# Являются ли паросочетания в полном графе семейством независимых множеств некоторого матроида?
# Рассмотрим кратчайшие пути из $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$ - матроид.
# Для каких универсальных матроидов существует изоморфный ему матричный матроид?
# Докажите, что матроид Вамоса не является представимым ни над каким полем.
# Аксиоматизация циклами, часть 1. Пусть множество $\mathcal C$ удовлетворяет условиям: оно не содержит пустое множество, ни один его элемент не является подмножеством другого, и если $C_1 \in \mathcal C$, $C_2 \in \mathcal C$, тогда для любого $p \in C_1 \cap C_2$ найдется $C_3 \in \mathcal C$, $C_3 \subset C_1 \cup C_2 \setminus p$. Назовем псевдонезависимым множество, не содержащее в качестве подмножества элемента $\mathcal C$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
# Аксиоматизация циклами, часть 2. Докажите, что множество циклов матроида из предыдущего задания совпадает с множеством $\mathcal C$.
# Аксиоматизация рангами, часть 1. Пусть функция $r : 2^X \to \mathbb{Z}^+$ удовлетворяет свойствам: (1) $r(A) \le |A|$, (2) если $A \subset B$, то $r(A) \le r(B)$, (3) для всех множеств $A$ и $B$ выполнено $r(A \cup B) + r(A \cap B) \le r(A) + r(B)$. Назовем псевдонезависимым множество, для которого $r(A) = |A|$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
# Аксиоматизация рангами, часть 2. Докажите, что ранговая функция матроида из предыдущего задания совпадает с функцией $r$.
# Замыканием множества $\langle A \rangle$ называется множество $\langle A \rangle = A \cup \{p \,|\, r(A \cup p) = r(A)\}$. Как устроено замыкание в графовом матроиде?
# Как устроено замыкание в матричном матроиде?
# Докажите, что если $A$ независимо, то для любого $p \in A$ выполнено $p \not\in \langle A \setminus p\rangle$.
# Докажите теорему о замыканиях: (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$
# Аксиоматизация замыканиями часть 1. Пусть функция $span : 2^X \to 2^X$ удовтелворяет свойствам (1)-(4) из предыдущего задания для $\langle \rangle$. Назовем псевдонезависимым множество $A$, если для любого $p \in A$ выполнено $p \not\in span(A \setminus p)$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
# Аксиоматизация замыканиями часть 2. Докажите, что функция замыкания в матроиде из предыдущего задания совпадает с $span$.
# Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую констркуцию: $M^* = \langle X, \{A \,|\, \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
# Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом?
# Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
# Докажите, что двойственный матроид к $K_5$ не является графовым.
# Докажите, что двойственный матроид к $K_{3,3}$ не является графовым.
# Когда двойственный к графовому матроид является графовым?
# Будем называть два элемента $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$ независимо.
# Сверхсильная теорема о базах. Докажите, что для любых двух различных баз $A$ и $B$ и элемента $x \in A \subset B$ найдётся $y \in B \subset A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
# Проекция матроида. Пусть $M = \langle X, I \rangle$ - матроид, $f : X \to Y$ - произвольная функция. Обратите внимание, что нет необходимости, чтобы $f$ была инъекцией или сюрьекцией. Построим конструкцию $f(M)$ как пару из носителя $Y$ и семейства множеств $f(I) = \{ f(A) \,|\, A \in I\}$. Докажите, что $f(M)$ является матроидом.
# Объединение матроидов. Объединением матроидов $M_1 = \langle X, I_1\rangle$ и $M_2 = \langle X, I_2\rangle$ называется конструкция $M = \langle X, I\rangle$, где $A \in I$, если найдутся такие $A_1 \in I_1$ и $A_2 \in I_2$, где $A = A_1 \cup A_2$. Докажите, что объединение матроидов является матроидом. Указание: рассмотрите объединение матроидов как проекцию суммы матроидов.
# Обратная лемма о замене. Рассмотрим матроид. Докажите, что если $A$ независимо и $B$ независимо, $|A| = |B|$, то в графе замен для множества $A$ найдется полное паросочетание на $A \oplus B$.
Анонимный участник

Навигация