| Текущая версия |
Ваш текст |
| Строка 153: |
Строка 153: |
| | # Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$. | | # Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$. |
| | # Пусть $p = \frac dn$. Докажите, что в $G(n, p)$ каждая вершина а.п.н. принадлежит не более, чем одному треугольнику. | | # Пусть $p = \frac dn$. Докажите, что в $G(n, p)$ каждая вершина а.п.н. принадлежит не более, чем одному треугольнику. |
| − | # Пусть $p = \omega(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$. | + | # Пусть $p = \omega(n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$. |
| | # Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}n)$? | | # Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}n)$? |
| | # Докажите, что $G(n, \frac dn), d > 1$ а.п.н. содержит индуцированный путь длины $\sqrt{\log n}$. | | # Докажите, что $G(n, \frac dn), d > 1$ а.п.н. содержит индуцированный путь длины $\sqrt{\log n}$. |
| | # Подберите $p(n)$ и приведите пример случайной величины $X$ в модели случайного графа $G(n, p)$, что $EX \to \infty$, но $\mathcal{P}(X = 0) \nrightarrow 0$. | | # Подберите $p(n)$ и приведите пример случайной величины $X$ в модели случайного графа $G(n, p)$, что $EX \to \infty$, но $\mathcal{P}(X = 0) \nrightarrow 0$. |
| − | # Для каких $p$ граф $G(n, p)$ а.п.н. не содержит $K_k$ (надо привести пороговую асимптотику)?
| |
| − | # Докажите, что если $k = \frac{\log n}{\log\log n}$, то $k! \le n$.
| |
| − | # Покажите, что в первой доле случайного двудольного графа $G(n, n, 1/n)$ с вероятностью, не стремящейся к нулю, существует вершина степени $\frac{\log n}{\log \log n}$.
| |
| − | # Зачем условие двудольности в предыдущей задаче? Покажите, что его можно убрать, в случайном графе $G(n, 1/n)$ с вероятностью, не стремящейся к нулю, существует вершина степени $\frac{\log n}{\log \log n}$.
| |
| − | # Докажите, что $G(n, 1/n)$ а.п.н. не содержит вершины степени больше $\frac{6\log n}{\log \log n}$. Указание, используйте приближение биномиального распределения Пуассоном и факт, что $k! \ge (k/e)^k$.
| |
| − | # Пусть $p = o(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. не содержит циклов.
| |
| − | # Пусть $p = \omega(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. содержит цикл.
| |
| − | # Пусть $p = \frac dn$. Что можно сказать про наличие циклов в $G(n, p)$?
| |
| − | # Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = o(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. не содержит полного паросочетание. Указание: используйте лемму Холла.
| |
| − | # Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = \omega(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. содержит полное паросочетание. Указание: используйте лемму Холла.
| |
| − | # Указание: в этом и следующих заданиях используйте вероятностный метод. Если вероятность, что объект обладает некоторым свойством, больше 0, то существует объект с таким свойством. Если матожидание числа объектов с некоторым свойством больше 0, то существует объект с таким свойством. Число Рамсея $R(a, b)$ - величина, такая что граф, содержащий хотя бы $R(a, b)$ вершин обязательно содержит или клику размера $a$ или независимое множество размера $b$. Оцените сверху вероятность, что граф из $G(n, \frac 12)$ содержит клику размера $k$ или независимое множество размера $k$. Сделайте вывод о нижней границе на число Рамсея: $R(k, k) \ge 2^{k/2-1}$.
| |
| − | # Докажите, что существует турнир, в котором как минимум $\frac {n!}{2^{n-1}}$ гамильтоновых путей.
| |
| − | # Докажите, что любой граф с $n$ вершинами и $m$ ребрами содержит двудольный подграф с как минимум $\frac m2$ ребрами.
| |
| − | # Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ существует независимое множество размера $(2 - \varepsilon) \log_2 n$.
| |
| − | # Пусть граф $G$ с $n$ вершинами и $m \ge 4n$ ребрами изображен на плоскости, причем никакие три ребра не пересекаются в одной точке, и никакое ребро не содержит вершину как свою внутреннюю точку. Обозначим как $c$ число попарных пересечений ребер вне вершин. Докажите, что $c \ge \frac{m^3}{64n^2}$.
| |
| − | # Пусть на плоскости выбрано $n$ точек, обозначим как $l$ число прямых, каждая из которых содержит хотя бы $k+1$ из заданных точек ($1 \le k \le 2\sqrt{2n}$). Докажите, что $l \le 32n^2/k^3$.
| |
| − | # Матроид, стянутый по элементу. Пусть $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$ - матроид.
| |
| − | # Для каких универсальных матроидов существует изоморфный ему матричный матроид?
| |
| − | # Докажите, что матроид Вамоса не является представимым ни над каким полем.
| |
| − | # Проекция матроида. Пусть $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$ также независимо.
| |
| − | # Дайте альтернативное определение параллельных элементов на языке баз.
| |
| − | # Докажите, что свойство быть параллельными является транзитивным отношением.
| |
| − | # Как устроено замыкание в графовом матроиде?
| |
| − | # Как устроено замыкание в матричном матроиде?
| |
| − | # Докажите, что если $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^*$ является матроидом.
| |
| − | # Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом.
| |
| − | # Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
| |
| − | # Докажите, что двойственный матроид к $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$ обе являются базами.
| |
