Редактирование: Список заданий по ДМ 2к 2021 осень

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 188: Строка 188:
 
# Напишите генератор графов $G(n, p)$ на вашем любимом языке программирования и примените в этом и последующих заданиях. Проведите численные эксперименты с генератором для различных значений $n$ и $p$, соотнесите результаты с теорией, которую вы узнали на лекциях. В качестве ответа на задание продемонстрируйте графики зависимости вероятности от $p$, другие результаты численных экспериментов, можно также запускать программу с демонстрацией результатов запуска на проекторе. Проанализируйте появление треугольников для $p=\frac cn$ в зависимости от константы $c$.
 
# Напишите генератор графов $G(n, p)$ на вашем любимом языке программирования и примените в этом и последующих заданиях. Проведите численные эксперименты с генератором для различных значений $n$ и $p$, соотнесите результаты с теорией, которую вы узнали на лекциях. В качестве ответа на задание продемонстрируйте графики зависимости вероятности от $p$, другие результаты численных экспериментов, можно также запускать программу с демонстрацией результатов запуска на проекторе. Проанализируйте появление треугольников для $p=\frac cn$ в зависимости от константы $c$.
 
# Продемонстрируйте появление свойства ""диаметр 2"" при $p=\sqrt{2 \ln n/n}$.
 
# Продемонстрируйте появление свойства ""диаметр 2"" при $p=\sqrt{2 \ln n/n}$.
# Проанализируйте исчезновение изолированных вершин и появление связности на одном графике.
+
# Проанализируйте исчезновение изолированих вершин и появление связности на одном графике.
# Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.
 
# Постройте матроид с 5 элементами и 12 базами.
 
# Матроид с выброшенным элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются независимые множества исходного матроида, которые не содержали $x$. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A | A \in I, x \notin 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 \ne y$, то $M\setminus x/y=M/y\setminus x$
 
# Урезанный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M|_k$ следующую констркуцию: $M|_k = \langle X, \{A | A \in I, |A| \le k \}\rangle$. Докажите, что $M|_k$ является матроидом.
 
# Прямая сумма матроидов. Пусть $X$ и $Y$ - непересекающиеся множества, $M_1$ - матроид с носителем $X$ и $M_2$ - матроид с носителем $Y$. Построим новый матроид, назовем носителем объединение $X \cup Y$, независимыми объявим множества, которые являются объединением независимого из $M_1$ и независимого из $M_2$. Докажите, что прямая сумма матроидов является матридом.
 
# Представьте разноцветный матроид в виде прямой суммы универсальных матроидов.
 
# Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
 
# Являются ли паросочетания в полном графе семейством независимых множеств некоторого матроида?
 
# Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
 
# Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксиомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
 
# Пусть $M$ - предматроид. Как и в матроиде будем называть базой множества максимальное по включению подмножество из $I$. Докажите, что если для каждого множества $A$ все его базы равномощны, то $M$ - матроид.
 
# Для каких универсальных матроидов существует изоморфный ему матричный матроид?
 
# Проекция матроида. Пусть $M = \langle X, I \rangle$ - матроид, $f : X \to Y$ - произвольная функция. Обратите внимание, что нет необходимости, чтобы $f$ была инъекцией или сюрьекцией. Построим конструкцию $f(M)$ как пару из носителя $Y$ и семейства множеств $f(I) = \{ f(A) \,|\, A \in I\}$. Докажите, что $f(M)$ является матроидом.
 
# Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
 
# Дайте альтернативное определение параллельных элементов на языке баз.
 
# Докажите, что отношение "быть параллельными" является транзитивным.
 
# (для 34-35) Как устроено замыкание в графовом матроиде?
 
# (для 34-35) Как устроено замыкание в матричном матроиде?
 
# Докажите, что если $A$ независимо, то для любого $p \in A$ выполнено $p \not\in \langle A \setminus p\rangle$.
 
# Докажите, что если $A \subset B$, то $\langle A \rangle \subset \langle B \rangle$.
 
# Докажите, что $\langle \langle A \rangle \rangle = \langle A \rangle$
 
# Докажите, что если $q \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^*$ является матроидом.
 
# Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом.
 
# Докажите, что двойственный к матричному матроид изоморфен матричному для некоторой матрицы. Как устроена его матрица?
 
# В этой и следующих задача граф для графового матроида может содержать кратные ребра. Докажите, что двойственный к графовому матроиду колеса $C_4 + K_1$ изоморфен графовому для некоторого графа
 
# Докажите, что двойственный к графовому матроиду графа $K_{2, 3}$ изоморфен графовому для некоторого графа
 
# Докажите, что двойственный матроид к графовому на $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 \setminus B$ найдётся $y \in B \setminus A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
 
# Доказать, что $M^{**}=M$
 
# Один студент считает, что xor двух циклов обязательно содержит цикл. Доказать или опровергнуть.
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)