| Текущая версия |
Ваш текст |
| Строка 46: |
Строка 46: |
| | # Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$. | | # Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$. |
| | # Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев. | | # Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев. |
| − | # Обобщение формулы Кэли. Пусть дан полный граф, и остовный лес в нём, компоненты связности леса состоят из $c_1, c_2, \ldots, c_k$ вершин. Докажите, что число способов добавить ребра, чтобы получилось остовное дерево, равно $c_1 c_2 \ldots c_k (c_1+c_2+\ldots+c_k)^{k-2}$. | + | # Обобщение формулы Кэли. Пусть дан полный граф из $n$ вершин, и лес в нём, компоненты связности леса имеют размеры $c_1, c_2, \ldots, c_k$. Докажите, что число способов добавить ребра, чтобы получилось дерево, равно $c_1 c_2 \ldots c_k (c_1+c_2+\ldots+c_k)^{k-2}$. |
| | # Для $n \ge 2$, найдите формулу для количества остовных деревьев $K_n$, содержащих ребро $1 - 2$, | | # Для $n \ge 2$, найдите формулу для количества остовных деревьев $K_n$, содержащих ребро $1 - 2$, |
| | # Дан код Прюфера дерева. Найдите степень каждой вершины, не восстанавливая дерево явно. | | # Дан код Прюфера дерева. Найдите степень каждой вершины, не восстанавливая дерево явно. |
| | # Даны числа $d_1, d_2, \ldots, d_n$. Докажите, что количество деревьев, в которых $deg(1) = d_1$, ..., $deg(n) = d_n$ равно $\frac {(n-2)!} {\prod (d_i - 1)!}$ | | # Даны числа $d_1, d_2, \ldots, d_n$. Докажите, что количество деревьев, в которых $deg(1) = d_1$, ..., $deg(n) = d_n$ равно $\frac {(n-2)!} {\prod (d_i - 1)!}$ |
| | # Обобщите матричную теорему Кирхгофа для следующей задачи: дан ориентированный граф и вершина $r$, нужно найти количество корневых деревьев с корнем в $r$. | | # Обобщите матричную теорему Кирхгофа для следующей задачи: дан ориентированный граф и вершина $r$, нужно найти количество корневых деревьев с корнем в $r$. |
| − | # Граф называется произвольно вычерчиваемым из вершины $u$, если следующая процедура всегда приводит к эйлеровому циклу: начиная с вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, по которому ранее не проходили. Докажите, что эйлеров граф является произвольно вычерчиваемым из $u$, если любой его простой цикл содержит $u$.
| |
| − | # Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то $u$ имеет максимальную степень в $G$.
| |
| − | # Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то либо $u$ - единственная точка сочленения в $G$, либо в $G$ нет точек сочленения.
| |
| − | # Порожденным (также индуцированным) подграфом называется подграф, полученный удалением некоторого множества вершин и всех инцидентных ребер. Докажите или опровергните, что если $G$ содержит порожденный тета-подграф (две вершины, соединенные тремя путями произвольной длины), то $G$ не гамильтонов.
| |
| − | # Обозначим как $G^3$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 3. Докажите, что если $G$ связен, то $G^3$ гамильтонов.
| |
| − | # Граф называется произвольно гамильтоновым, если следующая процедура всегда приводит к гамильтонову циклу: начиная с произвольной вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, другой конец которого мы ранее не посещали, либо обратно в вершину $u$, если непосещенных соседей нет. Опишите все произвольно гамильтоновы графы.
| |
| − | # Будем называть последовательность $(d_1, \ldots, d_n)$ степенной последовательностью, если существует граф с такими степенями вершин. Приведите критерий, проверяемый за полиномиальное время, что заданная последовательность является степенной.
| |
| − | # Теорема "Антихватала". Докажите, что если для степенной последовательности не выполнено условие теоремы Хватала, то найдется граф со степенной последовательностью, мажорирующей данную, не содержащий гамильтонова цикла.
| |
| − | # Докажите, что если сумма степеней любых двух несмежных вершин графа $G$ не меньше $n+1$, то любые две различные вершины $G$ можно соединить гамильтоновым путем.
| |
| − | # Реберным графом для графа $G$ называется граф $G_E$, множество вершин которого совпадает с множеством ребер исходного графа, два ребра $e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. Докажите или опровергните, что если $G$ является эйлеровым, то реберный граф является гамильтоновым.
| |
| − | # Докажите или опровергните, что если $G_E$ является гамильтоновым, то граф $G$ является эйлеровым.
| |
| − | # В каком случае ребра реберного графа можно разбить на полные подграфы таким образом, чтобы каждая вершина принадлежала в точности двум из подграфов?
| |
| − | # Выразите число треугольников в реберном графе $G_E$ через число треугольников графа $G$ и набор его степеней.
| |
| − | # В каком случае связный граф $G$ имеет регулярный реберный граф?
| |
| − | # Постройте связный граф $G$ с $n \ge 4$ вершинами, для которого граф $G_E$ не эйлеров, а граф $(G_E)_E$ эйлеров.
| |
| − | # Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $((G_E)_E)_E$ эйлеров, то $(G_E)_E$ эйлеров.
| |
| − | # Постройте минимальный по числу ребер граф, в реберном графе которого нет гамильтонова цикла.
| |
| − | # Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий для каждого ребра графа $G$ хотя бы одну вершину, ему инцидентную.
| |
| − | # Обозначим как $\lambda(G)$ минимальное число ребер, которое нужно удалить в графе, чтобы он потерял связность, $\kappa(G)$ - минимальное число вершин, которое нужно удалить в графе, чтобы он потерял связность (для полного графа полагаем $\kappa(G)=n-1$). Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
| |
| − | # Докажите. что для любых $1 \le \kappa(G) \le \lambda(G) \le \delta(G)$ существует граф $G$ с такими параметрами.
| |
| − | # Докажите, что не существует графов с $\kappa(G) = 3$ и $7$ ребрами.
| |
| − | # Пусть $G$ - полный двудольный граф, за исключением $K_{2,2}$. Докажите $\lambda(G)=\delta(G)$, почем единственный способ удалить $\lambda(G)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин.
| |
| − | # Графы $G_1$, содержащий $n_1$ вершин и $m_1$ ребер, и $G_2$, содержащий $n_2$ вершин и $m_2$ ребер, гомеоморфны. Докажите, что $n_1+m_2 = n_2+m_1$.
| |
| − | # Рассмотрим параметрически заданную замкнутую кривую $\phi(t)$, будем говорить, что она имеет самопересечение, если есть точка на кривой, которая порождается двумя различными значениями параметра $t_1$ и $t_2$, причем в окрестности этой точки фрагменты кривой в окрестности параметра $t_2$ лежат по разную сторону от кривой в окрестности параметра $t_1$. Докажите, что планарный эйлеров граф содержит эйлеров цикл, не имеющий самопересечений.
| |
| − | # Приведите пример вершинно двухсвязного планарного графа, который не является гамильтоновым.
| |
| − | # Докажите, что планарный четырехсвязный граф гамильтонов.
| |
| − | # Пусть $G$ - планарный граф, в котором каждый треугольник ограничивает область, не содержащую ребер, причем добавление любого ребра нарушает это свойство. Докажите, что $G$ гамильтонов.
| |
| − | # Докажите, что любой трехсвязный планарный граф имеет остов, у которого наибольшая степень равна 3.
| |
| − | # Докажите, что все колеса самодвойственны.
| |
| − | # Докажите, что в планарном графе $O(n)$ треугольников.
| |
| − | # Докажите, что можно ориентировать ребра планарного графа так, что $deg^-(v) \le 5$ для всех вершин $v$.
| |
| − | # Докажите, что можно ориентировать ребра планарного графа так, что $deg^-(v) \le 3$ для всех вершин $v$.
| |
| − | # Уложите четырехмерный куб на поверхности тора
| |
| − | # Уложите $K_7$ на поверхности тора
| |
| − | # Докажите, что $K_8$ нельзя уложить на поверхности тора
| |
| − | # Найдите максимальное $k$, что граф $K_k$ можно уложить на сфере с двумя ручками.
| |
| − | # Докажите, что для любого $m$ существует $k$, такое что граф с $K_k$ нельзя уложить на сфере с $m$ ручками.
| |
| − | # Посчитать хроматический многочлен цикла $C_n$
| |
| − | # Посчитать хроматический многочлен колеса $C_n + K_1$.
| |
| − | # Посчитать хроматический многочлен полного двудольного графа $K_{n,m}$.
| |
| − | # Докажите, что если хроматический многочлен графа равен $t(t-1)^{n - 1}$, то граф является деревом.
| |
| − | # Приведите пример двух связных графов, которые не являются деревьями, не являются изоморфными и имеют одинаковые хроматические многочлены.
| |
| − | # Докажите, что если длина максимального простого нечетного цикла в $G$ есть $k$, то $\chi(G)\le k + 1$.
| |
| − | # Если степени вершин графа $G$ равны $d_1 \ge d_2 \ge \ldots \ge d_n$, то $\chi(G)\le \max\min\{i, d_i+1\}$.
| |
| − | # Докажите или опровергните, что если граф $G$ с $n$ вершинами содержит гамильтонов цикл, причем ему принадлежат не все ребра графа, то (а) $\chi(G) \le 1 + n/2$ (б) $\chi(G) \ge 1 + n/2$ .
| |
| − | # Конъюнкцией $G_1 \wedge G_2$ графов называется граф с $V = V_1 \times V_2$, $(u_1, u_2)-(v_1, v_2) \in E$, если $u_1v_1 \in E_1$ и $u_2v_2\in E_2$. Доказать, что хроматическое число конъюнкции $G_1\wedge G_2$ графов $G_1$ и $G_2$ двух графов не превосходит хроматических чисел этих графов.
| |
| − | # Рассмотрим связный граф $G$, не являющийся простым циклом нечетной длины, все простые циклы которого нечетны. Обозначим как $\chi'(G)$ минимальное число цветов, в которое можно раскрасить ребра граф $G$, чтобы ни в какую вершину не входило ребер одного цвета. Докажите, что $\chi'(G)=\Delta(G)$.
| |
| − | # Докажите, что в любой раскраске реберного графа каждая вершина смежна не более чем с двумя вершинами одного цвета
| |
| − | # Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
| |
| − | # Доказать формулу Уитни: пусть $G$ - обыкновенный $(n, m)$ - граф. Тогда коэффициент при $x^i$, где $1\le i\le n$ в хроматическом многочлене $P_G(x)$ равен $\sum \limits_{j=0}^{m}{(-1)^jN(i, j)}$, где $N(i, j)$ - число остовных подграфов графа $G$, имеющих $i$ компонент связности и $j$ рёбер.
| |
| − | # Граф называется однозначно раскрашиваемым, если любые две его раскраски в $\chi(G)$ цветов совпадают с точностью до переименования цветов. Приведите пример однозначно раскрашиваемого связного графа и связного графа, который не является однозначно раскрашиваемым
| |
| − | # Какое минимальное число вершин может быть в однозначно раскрашиваемом в 3 цвета графе, отличном от полного графа?
| |
| − | # Какое минимальное число ребер может быть в однозначно раскрашиваемом в $k$ цветов графе с $n$ вершинами?
| |
| − | # Докажите, что существует такое $\alpha>1$, что у любого планарного графа c $n$ есть хотя бы $\alpha^n$ раскрасок в 5 цветов.
| |
| − | # Доказать или опровернгнуть: любое вершинное покрытие содержит как подмножество минимальное по мощности вершинное покрытие.
| |
| − | # Докажите, что $\alpha(G) \ge \frac{n}{1+\Delta(G)}$.
| |
| − | # Докажите, что $\alpha(G) \ge \sum (1 + \deg u)^{-1}$.
| |
| − | # Как может поменяться $\alpha(G)$ при удалении ребра? Удалении вершины? Добавлении ребра?
| |
| − | # Верно ли, что для двудольного графа значение $\alpha(G)$ равно размеру максимальной доли?
| |
| − | # Докажите, что $G$ двудольный тогда и только тогда, когда для любого $H$ - подграфа $G$ выполнено $\alpha(H) \ge |VH|/2$ ($VH$ - множество вершин графа $H$).
| |
| − | # Докажите, что если в дереве расстояние между двумя любыми листьями четно, то в нем существует единственное максимальное по числу вершин независимое множество. Верно ли обратное?
| |
| − | # Зафиксируем $n$ и $k$. Рассмотрим граф, удовлетворяющий следующим условиям: (1) граф $G$ содержит $n$ вершин; (2) $\alpha(G) \le k$. Среди таких графов рассмотрим граф с минимальным числом ребер. Этот граф называется граф Турана. Докажите, что в графе Турана любые две смежные вершины имеют равную степень.
| |
| − | # Степень любых двух несмежных вершин в графе Турана отличается не более чем на $1$.
| |
| − | # Оцените, сколько ребер в графе Турана.
| |
| − | # Граф называется $\alpha$-критическим, если удаление любого ребра увеличивает $\alpha(G)$. Приведите пример $\alpha$-критического и не $\alpha$-критического графа.
| |
| − | # Докажите, что в любом дереве, кроме $K_2$ существует минимальное по числу вершин вершинное покрытие, включающее все вершины, соседние с листьями.
| |
| − | # Доминирующим множеством в графе называется множество вершин, такое что каждая вершина либо входит в это множество, либо имеет соседа в этом множестве. Докажите, что независимое множество вершин является максимальным по включению если и только если оно является доминирующим.
| |
| − | # Обозначим размер минимального доминирующего множества в графе как $\gamma(G)$. Как связаны $\alpha(G)$ и $\gamma(G)$?
| |
| − | # Докажите, что если в графе $G$ нет изолированных вершин, и $A$ - минимальное по включению доминирующее множество в $G$, то существует $B$, не имеющее общих вершин с $A$, также являющееся минимальным по включению доминирующим множеством в $G$.
| |
| − | # Обозначим размер минимального по мощности покрывающего множества в графе как $\beta(G)$. Как связаны $\gamma(G)$ и $\beta(G)$?
| |
| − | # Пусть $G$ - связный кубический граф, в котором не более двух мостов. Тогда в $G$ существует совершенное паросочетание.
| |
| − | # Приведите пример связного кубического графа, содержащего три моста, в котором нет совершенного паросочетания.
| |
| − | # $k$-факторизацией графа называется разбиение множество ребер графа на его $k$-факторы. Докажите, что $K_4$ имеет единственную 1-факторизацию.
| |
| − | # Найдите число $1$-факторизаций графа $K_6$.
| |
| − | # Найдите число $1$-факторизаций графа $K_{3,3}$.
| |
| − | # Найдите число $1$-факторов графа $K_{2n}$.
| |
| − | # Докажите, что граф $K_{6n-2}$ имеет 3-факторизацию.
| |
| − | # Докажите, что граф $K_{4n+1}$ имеет 4-факторизацию.
| |
| − | # Докажите, что граф $K_9$ представим в виде объединения 4 гамильтоновых циклов.
| |
| − | # Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Пусть $G'$ получен из $G$ удалением не более чем $k - 1$ ребер. Тогда $G'$ содержит совершенное паросочетание. Указание: используйте теорему Татта.
| |
| − | # Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Тогда для любого ребра $uv$ существует совершенное паросочетание, содержащее $uv$.
| |
| − | # Докажите, что если $G$ - регулярный граф четной степени, то у него есть 2-фактор.
| |
| − | # Пусть $r<k$ и хотя бы одно из них нечетно. Докажите, что существует $G$ - регулярный граф степени $k$, у которого нет $r$-фактора.
| |
| − | # Множество $S\subset V$, для которого $odd(G\setminus S)-|S|=def(G)$, называется барьером. $A(G)$ является барьером графа. Приведите пример графа, в котором $A(G)$ не является максимальным по включению барьером.
| |
| − | # Приведите пример графа, в котором $A(G)$ не является минимальным по включению барьером.
| |
| − | # Докажите, что пересечение двух максимальных по включению барьеров также является барьером.
| |
| − | # Пусть $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$.
| |
| − | # Пусть $B$ - барьер графа $G$, причем $x \in B$. Тогда $B' = B \setminus x$ - барьер графа $G' = G \setminus x$.
| |
| − | # Докажите, что пересечение всех максимальных по включению барьеров $G$ равно $A(G)$.
| |
| − | # Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
| |
| − | # Докажите, что если связный граф $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
| |
| − | # Найдите математическое ожидание и дисперсию степени вершины в биномиальной модели $G(n, p)$.
| |
| − | # Равномерная модель $G(n, m)$ - каждый граф с $n$ вершинами и $m$ ребрами равновероятен. Найдите математическое ожидание степени вершины в равномерной модели $G(n, m)$.
| |
| − | # Найдите дисперсию степени вершины в равномерной модели $G(n, m)$.
| |
| − | # Найдите вероятность, что граф в равномерной модели $G(n, m)$ является деревом ($m = n - 1$).
| |
| − | # Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является деревом.
| |
| − | # Найдите вероятность, что граф в равномерной модели $G(n, m)$ является гамильтоновым циклом ($m = n$).
| |
| − | # Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является гамильтоновым циклом.
| |
| − | # Оцените центральный биномиальный коэффициент ${2n \choose n}$ снизу величиной порядка $c \frac {4^n}{\sqrt{n}}$, используя формулу Стирлинга.
| |
| − | # Рассмотрим число ребер $m$, такое что $m(n) \to \infty$ и ${n \choose 2} - m(n) \to \infty$, а также $p(n) = \frac {m(n)}{n \choose 2}$. Докажите, что вероятность того, что $G(n, p)$ имеет ровно $m$ ребер есть $\Omega(m^{-0.5})$.
| |
| − | # Рассмотрим свойство $A$, а и такие же $m(n)$ и $p(n)$, как в предыдущей задаче. Докажите, что $P(G(n, m) \in A) \le C \sqrt{m} P(G(n, p) \in A)$.
| |
| − | # Рассмотрим следующую модель генерации случайного графа. Сначала проведем каждое ребро с вероятностью $\frac 12$. Затем, для каждой пары вершин, между которыми не было проведено ребро на первом шаге, проведем ребро с вероятностью $\frac 13$. Предложите более простое описание этой модели в терминах моделей Эрдёша-Реньи.
| |
| − | # Свойство случайного графа называется, монотонным, если оно сохраняется при добавлении ребра. Рассмотрим монотонное свойство $A$ при фиксированном размере графа $n$. Докажите, что $P(G(n, p) \in A)$ возрастает при возрастании $p$.
| |
| − | # Придумайте такое свойство, что вероятность, что $G(n, \frac 12)$ обладает этим свойством, стремится к $\frac 14$.
| |
| − | # Придумайте такое свойство, что вероятность, что $G(n, \frac 12)$ обладает этим свойством, стремится к $\frac 13$.
| |
| − | # Пусть для некоторого свойства $A$ существует две функции $p_1(n)$ и $p_2(n)$, что для графа $G(n, p_1(n))$ свойство $A$ а.п.н. не выполняется, а для $G(n, p_2(n))$ свойство $A$ а.п.н. выполняется. Докажите, что существует функция $\tilde p(n)$, что для случайного графа $G(n, \tilde p(n))$ свойство $A$ выполняется с вероятностью, стремящейся к $\frac 12$.
| |
| − | # Подберите $p(n)$ и приведите последовательности случайных величин $X_n$ для $G(n, p)$, что $EX_n \to \infty$, но $\mathcal{P}(X_n = 0) \nrightarrow 0$.
| |
| − | # Докажите, что $G(n, \frac {2\ln n}{n})$ а.п.н. не содержит вершин степени 0.
| |
| − | # Рассмотрим модель случайного двудольного графа $G(n, n, p)$: из полного двудольного графа $K_{n,n}$ каждое ребро удаляется с вероятностью $1 - p$. Пусть $X$ -- количество изолированных вершин первой доли. Найдите $EX$ и $DX$.
| |
| − | # Докажите, что если $p = o(n^{-1.5})$, то $G(n, p)$ а.п.н. является объединением компонент связности размера 1 и 2.
| |
| − | # Докажите, что если $p = \omega(n^{-1.5})$, то $G(n, p)$ а.п.н. содержит путь длины 2.
| |
| − | # Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$.
| |
| − | # Пусть $p = o(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. не содержит цикл длины $k$.
| |
| − | # Пусть $p = \omega(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$.
| |
| − | # Пусть $p = o(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. не содержит циклов.
| |
| − | # Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}n)$?
| |
| − | # Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {\ln n}{2n})$ стремится к бесконечности.
| |
| − | # Найдите матожидание количества индуцированных подграфов $G(n, \frac dn)$, $d > 1$, которые являются путем длины $k = \sqrt{\log n}$.
| |
| − | # Для каких $p$ граф $G(n, p)$ а.п.н. не содержит $K_k$ (надо привести пороговую асимптотику)?
| |
| − | # Пусть $p = \frac dn$. Докажите, что в $G(n, p)$ каждая вершина а.п.н. принадлежит не более, чем одному треугольнику.
| |
| − | # Докажите, что в $G(n, \frac 12)$ а.п.н. не существует независимого множества размера $2 \log_2 n$
| |
| − | # Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.
| |
| − | # Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$.
| |
| − | # Найдите пороговую асимптотику, что граф $G(n, p)$ является эйлеровым или докажите, что её не существует
| |
| − | # Докажите, что если $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 = \frac dn$. Что можно сказать про наличие циклов в $G(n, p)$ в зависимости от $d$?
| |
| − | # Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = \omega(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. содержит полное паросочетание. Указание: используйте лемму Холла.
| |
| − | # Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = o(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. не содержит полное паросочетание. Указание: используйте лемму Холла.
| |
| − | # Пусть $p = \frac{\ln n + c}{n}$. Какой предел вероятности, что у $G(n,p)$ ровно $k$ изолированных вершин?
| |
| − | # Петя пытается спрятать в случайном графе клику размера $k$. Он берет граф с $n$ вершинами, $k$ из которых образуют клику, а остальных ребер нет, после чего проводит каждое из оставшихся ребер с вероятностью $1/2$. Вася хочет найти спрятанную Петей клику - выяснить, какие вершины ее образовывали. Для этого он выбирает $k$ вершин максимальной степени. Докажите, что если $k = \omega(\sqrt{n \ln n})$, то Вася а.п.н. найдет спрятанную Петей клику.
| |
| − | # Задача о наибольшем общем подграфе. Рассмотрим два графа, выбранных из распределения $G(n, 1/2)$. Найдем их общий индуцированный подграф размера $k$: выберем в каждом графе по $k$ вершин, оставим все ребра между ними, получившиеся графы должны быть изоморфны. Докажите, что наибольший общий подграф двух графов а.п.н. имеет размер не больше $4 \log_2 n$.
| |
| − | # Напишите генератор графов $G(n, p)$ на вашем любимом языке программирования и примените в этом и последующих заданиях. Проведите численные эксперименты с генератором для различных значений $n$ и $p$, соотнесите результаты с теорией, которую вы узнали на лекциях. В качестве ответа на задание продемонстрируйте графики зависимости вероятности от $p$, другие результаты численных экспериментов, можно также запускать программу с демонстрацией результатов запуска на проекторе. Проанализируйте появление треугольников для $p=\frac cn$ в зависимости от константы $c$.
| |
| − | # Продемонстрируйте появление свойства ""диаметр 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 двух циклов обязательно содержит цикл. Доказать или опровергнуть.
| |
