Список заданий по ДМ 2к 2018 осень — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 4 участников)
Строка 96: Строка 96:
 
# Докажите, что $G$ двудольный тогда и только тогда, когда для любого $H$ - подграфа $G$ выполнено $\alpha(H) \ge |VH|/2$ ($VH$ - множество вершин графа $H$).
 
# Докажите, что $G$ двудольный тогда и только тогда, когда для любого $H$ - подграфа $G$ выполнено $\alpha(H) \ge |VH|/2$ ($VH$ - множество вершин графа $H$).
 
# Докажите, что если в дереве расстояние между двумя любыми листьями четно, то в нем существует единственное максимальное по числу вершин независимое множество. Верно ли обратное?
 
# Докажите, что если в дереве расстояние между двумя любыми листьями четно, то в нем существует единственное максимальное по числу вершин независимое множество. Верно ли обратное?
# Зафиксируем $n$ и $k$. Рассмотрим граф, удовлетворяющpий следующим условиям: (1) граф $G$ содержит $n$ вершин; (2) $\alpha(G) \le k$. Среди таких графов рассмотрим граф с минимальным числом ребер. Этот граф называется граф Турана. Докажите, что в графе Турана любые две смежные вершины имеют равную степень.
+
# Зафиксируем $n$ и $k$. Рассмотрим граф, удовлетворяющpий следующим условиям: (1) граф $G$ содержит $n$ вершин; (2) $\alpha(G) \le k$. Среди таких графов рассмотрим граф с минимальным числом ребер. Этот граф называется граф Турана. Докажите, что в графе Турана любые две несмежные вершины имеют равную степень.
# Степень любых двух несмежных вершин в графе Турана отличается не более чем на $1$.
+
# Степень любых двух смежных вершин в графе Турана отличается не более чем на $1$.
 
# Оцените, сколько ребер в графе Турана.
 
# Оцените, сколько ребер в графе Турана.
 
# Граф называется $\alpha$-критическим, если удаление любого ребра увеличивает $\alpha(G)$. Приведите пример $\alpha$-критического и не $\alpha$-критического графа.
 
# Граф называется $\alpha$-критическим, если удаление любого ребра увеличивает $\alpha(G)$. Приведите пример $\alpha$-критического и не $\alpha$-критического графа.
Строка 140: Строка 140:
 
# Для каких универсальных матроидов существует изоморфный ему матричный матроид?
 
# Для каких универсальных матроидов существует изоморфный ему матричный матроид?
 
# Докажите, что матроид Вамоса не является представимым ни над каким полем.
 
# Докажите, что матроид Вамоса не является представимым ни над каким полем.
# Аксиоматизация циклами, часть 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$.
+
# Аксиоматизация циклами, часть 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$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
# Замыканием множества $\langle A \rangle$ называется множество $\langle A \rangle = A \cup \{p | r(A \cup p) = r(A)$. Как устроено замыкание в графовом матроиде?
+
# Аксиоматизация циклами, часть 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) $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)$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
# Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую констркуцию: $M^* = \langle X, \{A | \exists B $ - база $M,  A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
+
# Аксиоматизация замыканиями часть 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$ и $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$ независимо.
 
# Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $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$.

Текущая версия на 19:42, 4 сентября 2022

  1. Постройте граф с $n$ вершинами и $m$ ребрами. Здесь и далее "постройте граф с $n$ вершинами, ..." означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
  2. Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$.
  3. Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$.
  4. Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
  5. Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
  6. Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) > n$.
  7. Постройте двудольный граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) > n$.
  8. Пусть для двудольного графа выполнено условие: для любой пары не соединенных ребром вершин есть вершина, связанная с обеими этими вершинами. Как устроен такой граф?
  9. Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
  10. Граф называется кубическим, если степень всех вершин равна 3. Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
  11. Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
  12. Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
  13. Докажите, что каждый циклический путь нечетной длины содержит простой цикл.
  14. Докажите или опровергните, что объединение двух любых различных простых путей из вершины $u$ в вершину $v$ содержит цикл.
  15. Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
  16. Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
  17. Докажите или опровергните, что в связном графе все самые длинные простые пути имеют общую вершину.
  18. Обозначим как $\delta(G)$ минимальную степень вершины в графе. Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
  19. Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
  20. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
  21. Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем четных простых циклов.
  22. Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
  23. Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
  24. Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
  25. Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
  26. Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это $R^*$.
  27. Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
  28. Каждое дерево является двудольным графом. А какие деревья являются полными двудольными графами?
  29. Доказать, что следующие четыре утверждения для связного графа $G$ эквивалентны: (1) любое ребро является мостом (2) $G$ является деревом (3) любой блок $G$ является $K_2$ (4) любое непустое пересечение связных подграфов $G$ связно.
  30. Доказать, что следующие четыре утверждения для связного графа $G$ эквивалентны: (1) $G$ содержит ровно один простой цикл (2) число вершин и ребер $G$ совпадает (3) $G$ можно превратить в дерево удалением ровно одного ребра (4) множество ребер $G$, которые не являются мостами, образуют один простой цикл.
  31. Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
  32. Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
  33. Докажите, что если $v$ точка сочленения в $G$, то $v$ не точка сочленения в $\overline G$.
  34. Опишите все деревья с диаметром 2.
  35. Опишите все деревья с диаметром 3.
  36. Опишите дерево с кодом Прюфера $(i, i,\ldots , i)$.
  37. Опишите деревья, в коде Прюфера которых нет одинаковых чисел.
  38. Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.
  39. Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?
  40. Приведите пример графа с двумя непересекающимися остовными деревьями.
  41. Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами?
  42. Пусть связный граф $G$ имеет диаметр $d$. Докажите или опровергните, что у $G$ есть остовное дерево с диаметром $d$.
  43. Рассмотрим множество остовных деревьев связного графа $G$. Построим граф $S_G$, вершинами которого являются остовные деревья $G$, а две вершины $T_1$ и $T_2$ соединены ребром, если дерево $T_2$ можно получить из $T_1$ удалением одного ребра и добавлением другого. Докажите, что $S_G$ является связным.
  44. Докажите, что две вершины $T_1$ и $T_2$ в $S_G$ соединены ребром тогда и только тогда, когда их объединение содержит ровно один простой цикл.
  45. Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$.
  46. Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$.
  47. Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$.
  48. Зафиксируем дерево $T$. Рассмотрим функцию от вершины $x$: $d(x) = \sum_v dist(x, v)$, где $dist(x, v)$ - расстояние между вершинами $x$ и $v$ в ребрах. Пусть $y$ и $z$ - различные соседи вершины $x$. Докажите, что $2d(x) < d(y) + d(z)$.
  49. Центром дерева называется вершина $x$, для которой $max_v(dist(x, v))$ минимален. Докажите, что у дерева 1 или 2 центра, и любой центр дерева лежит на его любом диаметре.
  50. Барицентром дерева называется вершина $x$, для которой $\sum_v(dist(x, v))$ минимальная. Докажите, что у дерева 1 или 2 барицентра.
  51. Докажите, что для любого $k$ существует дерево, для которого расстояние между центром и барицентром не меньше $k$.
  52. Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев.
  53. Обозначим как $\lambda(G)$ минимальное число ребер, которое нужно удалить в графе, чтобы он потерял связность, $\kappa(G)$ - минимальное число вершин, которое нужно удалить в графе, чтобы он потерял связность (для полного графа полагаем $\kappa(G)=n-1$). Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
  54. Докажите. что для любых $1 \le \kappa(G) \le \lambda(G) \le \delta(G)$ существует граф $G$ с такими параметрами.
  55. Докажите, что не существует графов с $\kappa(G) = 3$ и $7$ ребрами.
  56. Пусть $G$ - полный двудольный граф, за исключением $K_{2,2}$. Докажите $\lambda(G)=\delta(G)$, почем единственный способ удалить $\lambda(G)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин.
  57. Посчитать хроматический многочлен цикла $C_n$
  58. Посчитать хроматический многочлен колеса $C_n + K_1$.
  59. Посчитать хроматический многочлен полного двудольного графа $K_{n,m}$.
  60. Докажите, что хроматический многочлен дерева равен $t(t-1)^{n - 1}$.
  61. Докажите, что если хроматический многочлен графа равен $t(t-1)^{n - 1}$, то граф является деревом.
  62. Приведите пример двух графов, которые не являются деревьями, не являются изоморфными и имеют одинаковые хроматические многочлены.
  63. Докажите, что если длина максимального простого нечетного цикла в $G$ есть $k$, то $\chi(G)\le k + 1$.
  64. Если степени вершин графа $G$ равны $d_1 \ge d_2 \ge \ldots \ge d_n$, то $\chi(G)\le \max\min\{i, d_i+1\}$.
  65. Докажите или опровергните, что если граф $G$ с $n$ вершинами содержит гамильтонов цикл, причем ему принадлежат не все ребра графа, то (а) $\chi(G) \le 1 + n/2$ (б) $\chi(G) \ge 1 + n/2$ .
  66. Конъюнкцией $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$ двух графов не превосходит хроматических чисел этих графов.
  67. Докажите, что при $n \ge 3$ $K_{n+1}$ является единственным связным регулярным графом степени $n$, который имеет хроматическое число $n+1$.
  68. Рассмотрим связный граф $G$, не являющийся простым циклом нечетной длины, все простые циклы которого нечетны. Обозначим как $\chi'(G)$ минимальное число цветов, в которое можно раскрасить ребра граф $G$, чтобы ни в какую вершину не входило ребер одного цвета. Докажите, что $\chi'(G)=\Delta(G)$.
  69. Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
  70. Доказать формулу Уитни: пусть $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$ рёбер.
  71. Графы $G_1$, содержащий $n_1$ вершин и $m_1$ ребер, и $G_2$, содержащий $n_2$ вершин и $m_2$ ребер, гомеоморфны. Докажите, что $n_1+m_2 = n_2+m_1$.
  72. Докажите, что планарный эйлеров граф содержит эйлеров цикл, не имеющий самопересечений.
  73. Приведите пример двухсвязного планарного графа, который не является гамильтоновым.
  74. Докажите, что планарный четырехсвязный граф гамильтонов.
  75. Пусть $G$ - планарный граф, в котором каждый треугольник ограничивает область, не содержащую ребер, причем добавление любого ребра нарушает это свойство. Докажите, что $G$ гамильтонов.
  76. Докажите, что любой трехсвязный планарный граф имеет остов, у которого наибольшая степень равна 3.
  77. Докажите, что все колеса самодвойственны.
  78. Найдите максимальное $k$, что граф $K_k$ можно уложить на торе.
  79. Найдите максимальное $k$, что граф $K_k$ можно уложить на сфере с двумя ручками.
  80. Докажите, что для любого $m$ существует $k$, такое что граф с $K_k$ нельзя уложить на сфере с $m$ ручками.
  81. Реберным графом для графа $G$ называется граф $G_E$, множество вершин которого совпадает с множеством ребер исходного графа, два ребра $e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. Докажите или опровергните, что если $G$ является эйлеровым, то реберный граф является гамильтоновым.
  82. Докажите или опровергните, что если $G_E$ является гамильтоновым, то граф $G$ является эйлеровым.
  83. В каком случае ребра реберного графа можно разбить на полные подграфы таким образом, чтобы каждая вершина принадлежала в точности двум из подграфов?
  84. Выразите число треугольников в реберном графе $G_E$ через число треугольников графа $G$ и набор его степеней.
  85. В каком случае связный граф $G$ имеет регулярный реберный граф?
  86. Постройте граф $G$ с $n \ge 4$ вершинами, для которого граф $G_E$ не эйлеров, а граф $G_E^2$ эйлеров.
  87. Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $G_E^2$ эйлеров, то и $G_E^3$ эйлеров.
  88. Постройте минимальный по числу вершин реберный граф, в котором нет гамильтонова цикла.
  89. Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий хотя бы одну вершину, инцидентную каждому ребру графа $G$.
  90. Доказать или опровернгнуть: любое вершинное покрытие содержит как подмножество минимальное по мощности вершинное покрытие.
  91. Доказать или опровергнуть: если в $G$ содержится реберно простой замкнутый путь, содержащий вершинное покрытие, то его реберный граф $E_G$ гамильтонов.
  92. Докажите, что $\alpha(G) \ge \frac{n}{1+\Delta(G)}$.
  93. Докажите, что $\alpha(G) \ge \sum (1 + \deg u)^{-1}$.
  94. Как может поменяться $\alpha(G)$ при удалении ребра? Удалении вершины? Добавлении ребра?
  95. Верно ли, что для двудольного графа значение $\alpha(G)$ равно размеру максимальной доли?
  96. Докажите, что $G$ двудольный тогда и только тогда, когда для любого $H$ - подграфа $G$ выполнено $\alpha(H) \ge |VH|/2$ ($VH$ - множество вершин графа $H$).
  97. Докажите, что если в дереве расстояние между двумя любыми листьями четно, то в нем существует единственное максимальное по числу вершин независимое множество. Верно ли обратное?
  98. Зафиксируем $n$ и $k$. Рассмотрим граф, удовлетворяющpий следующим условиям: (1) граф $G$ содержит $n$ вершин; (2) $\alpha(G) \le k$. Среди таких графов рассмотрим граф с минимальным числом ребер. Этот граф называется граф Турана. Докажите, что в графе Турана любые две несмежные вершины имеют равную степень.
  99. Степень любых двух смежных вершин в графе Турана отличается не более чем на $1$.
  100. Оцените, сколько ребер в графе Турана.
  101. Граф называется $\alpha$-критическим, если удаление любого ребра увеличивает $\alpha(G)$. Приведите пример $\alpha$-критического и не $\alpha$-критического графа.
  102. Докажите, что в любом дереве, кроме $K_2$ существует минимальное по числу вершин вершинное покрытие, включающее все вершины, соседние с листьями.
  103. Доминирующим множеством в графе называется множество вершин, такое что каждая вершина либо входит в это множество, либо имеет соседа в этом множестве. Докажите, что независимое множество вершин является максимальным по включению если и только если оно является доминирующим.
  104. Обозначим размер минимального доминирующего множества в графе как $\gamma(G)$. Как связаны $\alpha(G)$ и $\gamma(G)$?
  105. Докажите, что если в графе $G$ нет изолированных вершин, и $A$ - минимальное по включению доминирующее множество в $G$, то существует $B$, не имеющее общих вершин с $A$, также являющееся минимальным по включению доминирующим множеством в $G$.
  106. Обозначим размер минимального по мощности покрывающего множества в графе как $\beta(G)$. Как связаны $\gamma(G)$ и $\beta(G)$?
  107. $k$-факторизацией графа называется разбиение множество ребер графа на его $k$-факторы. Докажите, что $K_4$ имеет единственную 1-факторизацию.
  108. Найдите число $1$-факторизаций графа $K_6$.
  109. Найдите число $1$-факторизаций графа $K_{3,3}$.
  110. Найдите число $1$-факторов графа $K_{2n}$.
  111. Докажите, что граф $K_{6n-2}$ имеет 3-факторизацию.
  112. Докажите, что граф $K_{4n+1}$ имеет 4-факторизацию.
  113. Докажите, что граф $K_9$ представим в виде объединения 4 гамильтоновых циклов.
  114. Пусть $G$ - связный кубический граф, в котором не более двух мостов. Тогда в $G$ существует совершенное паросочетание.
  115. Приведите пример связного кубического графа, содержащего три моста, в котором нет совершенного паросочетания.
  116. Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Пусть $G'$ получен из $G$ удалением не более чем $k - 1$ ребер. Тогда $G'$ содержит совершенное паросочетание. Указание: используйте теорему Татта.
  117. Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Тогда для любого ребра $uv$ существует совершенное паросочетание, содержащее $uv$.
  118. Докажите, что если $G$ - регулярный граф четной степени, то у него есть 2-фактор.
  119. Пусть $r<k$ и хотя бы одно из них нечетно. Докажите, что существует $G$ - регулярный граф степени $k$, у которого нет $r$-фактора.
  120. Множество $S\subset V$, для которого $odd(G\setminus S)-|S|=def(G)$, называется барьером. $A(G)$ является барьером графа. Приведите пример графа, в котором $A(G)$ не является максимальным по включению барьером.
  121. Приведите пример графа, в котором $A(G)$ не является минимальным по включению барьером.
  122. Докажите, что пересечение двух максимальных по включению барьеров также является барьером.
  123. Пусть $x\in A(G)\cup C(G)$, $G'=G\setminus x$, $B'$ - барьер графа $G'$. Докажите, что $B=B'\cup x$ - барьер графа $G$. Следствие: любая вершина из $A(G) \cup C(G)$ входит в барьер графа $G$.
  124. Пусть $B$ - барьер графа $G$, тогда $B\cap D(G)$ пусто и все компоненты $D(G)$ являются подмножествами нечетных компонент связности графа $G\setminus B$.
  125. Пусть $B$ - барьер графа $G$, причем $x \in B$. Тогда $B' = B \setminus x$ - барьер графа $G' = G \setminus x$.
  126. Докажите, что пересечение всех максимальных по включению барьеров $G$ равно $A(G)$.
  127. Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
  128. Докажите, что если $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
  129. Предложите алгоритм нахождения множества Татта в двудольном графе за $\mathcal{O}(nm)$.
  130. Матроид, стянутый по элементу. Пусть $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$ является матроидом.
  131. Прямая сумма матроидов. Пусть $X$ и $Y$ - непересекающиеся множества, $M_1$ - матроид с носителем $X$ и $M_2$ - матроид с носителем $Y$. Построим новый матроид, назовем носителем объединение $X \cup Y$, независимыми объявим множества, которые являются объединением независимого из $M_1$ и независимого из $M_2$. Докажите, что прямая сумма матроидов является матридом.
  132. Представьте разноцветный матроид в виде прямой суммы универсальных матроидов.
  133. Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
  134. Является ли венгерский алгоритм вариантом алгоритма Радо-Эдмондса?
  135. Являются ли паросочетания в полном графе семейством независимых множеств некоторого матроида?
  136. Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
  137. Урезанный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M|_k$ следующую констркуцию: $M|_k = \langle X, \{A | A \in I, |A| \le k \}\rangle$. Докажите, что $M|_k$ является матроидом.
  138. Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксиомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
  139. Пусть $M$ - предматроид. Как и в матроиде будем называть базой множества максимальное по включению подмножество из $I$. Докажите, что если для каждого множества $A$ все его базы равномощны, то $M$ - матроид.
  140. Для каких универсальных матроидов существует изоморфный ему матричный матроид?
  141. Докажите, что матроид Вамоса не является представимым ни над каким полем.
  142. Аксиоматизация циклами, часть 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$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
  143. Аксиоматизация циклами, часть 2. Докажите, что множество циклов матроида из предыдущего задания совпадает с множеством $\mathcal C$.
  144. Аксиоматизация рангами, часть 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|$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
  145. Аксиоматизация рангами, часть 2. Докажите, что ранговая функция матроида из предыдущего задания совпадает с функцией $r$.
  146. Замыканием множества $\langle A \rangle$ называется множество $\langle A \rangle = A \cup \{p \,|\, r(A \cup p) = r(A)\}$. Как устроено замыкание в графовом матроиде?
  147. Как устроено замыкание в матричном матроиде?
  148. Докажите, что если $A$ независимо, то для любого $p \in A$ выполнено $p \not\in \langle A \setminus p\rangle$.
  149. Докажите теорему о замыканиях: (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$
  150. Аксиоматизация замыканиями часть 1. Пусть функция $span : 2^X \to 2^X$ удовтелворяет свойствам (1)-(4) из предыдущего задания для $\langle \rangle$. Назовем псевдонезависимым множество $A$, если для любого $p \in A$ выполнено $p \not\in span(A \setminus p)$. Докажите, что псевдонезависимые множества образуют семейство независимых множеств некоторого матроида.
  151. Аксиоматизация замыканиями часть 2. Докажите, что функция замыкания в матроиде из предыдущего задания совпадает с $span$.
  152. Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую констркуцию: $M^* = \langle X, \{A \,|\, \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
  153. Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом?
  154. Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
  155. Докажите, что двойственный матроид к $K_5$ не является графовым.
  156. Докажите, что двойственный матроид к $K_{3,3}$ не является графовым.
  157. Когда двойственный к графовому матроид является графовым?
  158. Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
  159. Дайте альтертанивное определение параллельных элементов на языке баз.
  160. Докажите, что свойство быть параллельными является отношением эквивалентности.
  161. Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $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$ независимо.
  162. Сверхсильная теорема о базах. Докажите, что для любых двух различных баз $A$ и $B$ и элемента $x \in A \subset B$ найдётся $y \in B \subset A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
  163. Проекция матроида. Пусть $M = \langle X, I \rangle$ - матроид, $f : X \to Y$ - произвольная функция. Обратите внимание, что нет необходимости, чтобы $f$ была инъекцией или сюрьекцией. Построим конструкцию $f(M)$ как пару из носителя $Y$ и семейства множеств $f(I) = \{ f(A) \,|\, A \in I\}$. Докажите, что $f(M)$ является матроидом.
  164. Объединение матроидов. Объединением матроидов $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$. Докажите, что объединение матроидов является матроидом. Указание: рассмотрите объединение матроидов как проекцию суммы матроидов.
  165. Обратная лемма о замене. Рассмотрим матроид. Докажите, что если $A$ независимо и $B$ независимо, $|A| = |B|$, то в графе замен для множества $A$ найдется полное паросочетание на $A \oplus B$.