Изменения

# Докажите, что $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.# Докажите, что все колеса самодвойственны.# Уложите четырехмерный куб на поверхности тора# Уложите $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}$.# Докажите, что если хроматический многочлен графа равен $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$ вершинами?# Доказать или опровернгнуть: любое вершинное покрытие содержит как подмножество минимальное по мощности вершинное покрытие.# Доказать или опровергнуть: если в $G$ содержится реберно простой замкнутый путь, содержащий вершинное покрытие, то его реберный граф $E_G$ гамильтонов.# Докажите, что $\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$. Рассмотрим граф, удовлетворяющpий следующим условиям: (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)$ является деревом ($m = n - 1$).# Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является деревом.# Найдите вероятность, что граф в равномерной модели $G(n, m)$ является гамильтоновым циклом ($m = n$).# Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является гамильтоновым циклом.# Докажите, что если $p = o(\frac{1}{n^2})$, то случайный граф $G(n, p)$ а.п.н. не имеет ребер (а.п.н. = асимптотически почти наверное = с вероятностью, стремящейся к 1).# Докажите, что если $p = \omega(\frac{1}{n^2})$, то случайный граф $G(n, p)$ а.п.н. имеет хотя бы одно ребро.# Пусть $p = \frac{c}{n^2}$ для некоторого $c$. Найдите вероятность того, $G(n, p)$ имеет хотя бы одно ребро.# Оцените центральный биномиальный коэффициент ${2n \choose n}$ снизу величиной порядка $\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 13$.# Пусть для некоторого свойства $A$ существует две функции $p_1(n)$ и $p_2(n)$, что для графа $G(n, p_1(n))$ свойство $A$ а.п.н. не выполняется, а для $G(n, p_2(n))$ свойство $A$ а.п.н. выполняется. Докажите, что существует функция $p'(n)$, что для случайного графа $G(n, p'(n))$ свойство $A$ выполняется с вероятностью, стремящейся к $\frac 12$.# Докажите, что $G(n, \frac {2\ln n}{n})$ а.п.н. не содержит изолированных вершин.# Рассмотрим модель случайного двудольного графа $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.# Выведите формулу вероятности того, что расстояние между фиксированными вершинами $u$ и $v$ больше двух.# Докажите, что $G(n, p)$ а.п.н имеет диаметр 2, если $p$ - константа.# Пусть $p = c \sqrt{ \frac {\ln n}{n}}$, $c > \sqrt{2}$. Покажите, что $G(n, p)$ а.п.н. имеет диаметр 2.# Докажите, что $G(n, p)$ а.п.н имеет диаметр больше 2, если $p = c \sqrt{ \frac {\ln n}{n}}$, $c < \sqrt{2}$.# Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$.# Пусть $p = \frac dn$. Докажите, что в $G(n, p)$ каждая вершина а.п.н. принадлежит не более, чем одному треугольнику.# Пусть $p = \omega(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$.# Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}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$ граф $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$обе являются базами.