Изменения

# ИзвестноДоказать или опровернгнуть: любое вершинное покрытие содержит как подмножество минимальное по мощности вершинное покрытие.# Докажите, что $\alpha(G) \ge \frac{n}{1+\Delta(G)}$.# Докажите, что у учителя есть $2\alpha(G) \ge \sum (1 + \deg u)^k{-1}$.# Как может поменяться $\alpha(G)$ при удалении ребра? Удалении вершины? Добавлении ребра?# Верно ли, что для двудольного графа значение $\alpha(G)$ равно размеру максимальной доли?# Докажите, что $G$ яблок двудольный тогда и только тогда, когда для некоторого целого неотрицательного любого $H$ - подграфа $G$ выполнено $\alpha(H) \ge |VH|/2$ ($VH$ - множество вершин графа $H$).# Докажите, что если в дереве расстояние между двумя любыми листьями четно, то в нем существует единственное максимальное по числу вершин независимое множество. Верно ли обратное?# Зафиксируем $n$ и $k$. На глазах у студентов он съедает одно яблокоРассмотрим граф, а остальное раздает ученикам А и Вудовлетворяющий следующим условиям: (1) граф $G$ содержит $n$ вершин; (2) $\omega(G) \le k$. Среди таких графов рассмотрим граф с максимальным числом ребер. Этот граф называется граф Турана. Докажите, чтобы ни один из них что в графе Турана любые две несмежные вершины имеют равную степень.# Степень любых двух смежных вершин в графе Турана отличается не виделболее чем на $1$.# Оцените, сколько получает другойребер в графе Турана.# Граф называется $\alpha$-критическим, если удаление любого ребра увеличивает $\alpha(G)$. А Приведите пример $\alpha$-критического и В не знают числа $k\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$-факторов графа $tK_{2n}$.# Докажите, а затем запускает алгоритм за что граф $K_{6n-2}$t^имеет 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$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).# Найдите $R(3, 4)$# Докажите, что $R(n, 3) \le (n^2+3)/2$# Найдите $R(3, 3, 3)$# На плоскости даны 6 точек, никакие 3 из которых не лежат на одной прямой и все попарные расстояния между которыми различны. Рассмотрим все треугольники с вершинами в этих точках. Докажите, что найдется отрезок, который в одном из этих треугольников является наибольшей стороной, а в другом - наименьшей. Какое значение # Обобщение теоремы Шура. Докажите, что для любого натурального $k$ найдется такое $n$, что в любой раскраске чисел от 1 до $n$ в $k$ цветов найдутся различные $x$ и $y$, такие что $x$, $y$ и $tx+y$ необходимо раскрашены в один цвет.# Докажите, что из 5 точек на плоскости, никакие три из которых не лежат на одной прямой, можно выбрать4, являющихся вершинами выпуклого четырехугольника.# Докажите, что для любого $n$ найдется $N$, чтобы минимизировать время работы получившегося алгоритма? Какое будет время работы?такое что из любых $N$ точек, никакие 3 из которых не лежат на одной прямой, можно выбрать вершины выпуклого $n$-угольника.# Докажите, что для любого $n$ найдется такое простое $p$, что существуют натуральные числа $x$, $y$ и $z$, не кратные $p$, что $x^n+y^n=z^n \pmod p$.# Докажите усиление теоремы Эрдёша: $R(k, k) \ge \frac{2^{k/2}\cdot k}{e\sqrt{2}}$# Докажите, что для любого достаточно большого $s$ выполнено $R(k, k) \ge s - {s \choose k}\cdot 2^{1-{k \choose 2}}$# Докажите, что в любой перестановке $n$ элементов найдется возрастающая последовательность из $\sqrt{n}$ элементов или убывающая последовательнтсть из $\sqrt{n}$ элементов.# Теорема Ван дер Вардена. Докажите, что для любых $n$ и $k$ найдется такое $W(n, k)$, что если числа от $1$ до $W(n, k)$ покрасить в $k$ цветов, то найдется арифметическая прогрессия длины $n$, покрашенная в один цвет.# Все клетки бесконечного листа клетчатой бумаги раскрасили в полном двоичном дереве высоты $hn$ цветов. Докажите, что найдутся четыре вершины прямоугольника со сторонами, параллельными осям координат, которые покрашены в один цвет.# Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что для любых $k$ и $l$ найдутся $k$ строк и $l$ столбцов, что все $kl$ их клеток пересечения покрашены в один и тот же цвет.# $P_k$ - путь длины $k-1$ (содержащий $k$ вершин и $k-1$ каждое ребро удаляется с вероятностью ). Найдите $R(P_3, P_3)$.# Найдите $R(P_4, P_4)$# Завершите доказательство теоремы Хватала, показав, что $R(T_m, K_n) \ge (n-1)(m-1)+1/2$# Покажите, что добавление ребра может сделать совершенный граф несовершенным# Покажите, что удалине ребра может сделать совершенный граф несовершенным# Докажите, что любой интервальный граф является хордальным# Докажите, что дополнение любого интервального графа является графом сравнений# Приведите пример хордального графа, который не является интервальным# Докажите, что хордальный граф является интервальным тогда и только тогда, когда его дополнение является графом сравнений (теорема Гилмора-Хоффмана)# Докажите, что граф $G$ является совершенным тогда и только тогда, когда $|H| \le \alpha(H)\omega(H)$ для любого $H$ - индуцированного подграфа $G$ (теорема Ловаса)# Докажите, что если $G$ является реберным графом, то путь от корня до листа сохраняется с вероятностью $\Thetachi(G) \in \{\omega(G), \omega(G)+1/h\}$.# Опишите графы, у которых реберный граф является совершенным# Докажите, что граф $G$ является совершенным тогда и только тогда, когда его любой непустой индуцированный подграф $H$ содержит независимое множество $A$, такое что $\omega(H \setminus A) < \omega(H)$. # Обобщите предыдущее заданиеРассмотрим граф $G$, если ребро удаляется с вероятностью такой что для любого индуцированного подграфа $H$ любая максимальная клика и любое максимальное независимое множество имеют общую вершину. Докажите, что $pG$совершенный.# С учетом Докажите, что $G$ обладает свойством из предыдущего задания модифицируйте алгоритм Каргера-Штайнатогда и только тогда, чтобы разветвляться когда накопленная вероятность ошибки достигнет $pG$ не содержит индуцированного пути из трех вершин (любые три вершины соединены либо 0, либо 1, либо 3 ребрами).# Рассмотрим совершенный граф $G$. Докажите, что можно покрыть все вершины графа независимыми множествами (обозначим семейство этих независимых множеств $\mathbb{I}$), а также покрыть все вершины графа кликами (обозначим семейство этих клик как $\mathbb{J}$, что для любых $A \in \mathbb{I}$ и $B \in \mathbb{J}$ выполнено $A \cap B \ne \emptyset$.# Рассмотрим совершенный граф $G$. Найдите зависимость времени работы от Заметим каждую его вершину $x$ на произвольный совершенный граф $G_x$ (вершины графов $G_x$ и $pG_y$соединены друг с другом, какое значение если было ребро $pxy$ оптимально выбрать?). Докажите, что получившийся граф является совершенным.# Предложите полиномиальный алгоритм проверки, что граф является хордальным.# Назовем разрез Предложите полиномиальный алгоритм поиска $\alpha(G)$ для хордального графа $G$.# Предложите полиномиальный алгоритм поиска $\chi(G)$ для хордального графа $G$.# Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.# Постройте матроид с 5 элементами и 12 базами.# Матроид с выброшенным элементом. Пусть $M$-оптимальнымматроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются независимые множества исходного матроида, которые не содержали $x$. Формально, если его размер не больше $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \alpha C_{minA \setminus x | A \in I, x \not\in 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$ - матроид. Обозначим как $C_M|_k$ следующую констркуцию: $M|_k = \langle X, \{minA | 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 \alphato Y$-оптимальный разрез произвольная функция. Обратите внимание, что нет необходимости, чтобы $f$ была инъекцией или сюрьекцией. Построим конструкцию $f(в зависимости от M)$ как пару из носителя $Y$ и семейства множеств $f(I) = \alpha{ 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 $ - база $nM, A \cap B = \varnothing\}\choose rangle$. Докажите, что $M^*$ является матроидом.# Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом.# Докажите, что двойственный к матричному матроид изоморфен матричному для некоторой матрицы. Как устроена его матрица?# В этой и следующих задача граф для графового матроида может содержать кратные ребра. Докажите, что двойственный к графовому матроиду колеса $C_4 + K_1$ изоморфен графовому для некоторого графа# Докажите, что двойственный к графовому матроиду графа $K_{2, 3}$ различных минимальных глобальных разрезовизоморфен графовому для некоторого графа# Докажите, что двойственный матроид к графовому на $K_5$ не изоморфен графовому ни для какого графа.# Докажите, что двойственный матроид к графовому на $K_{3,3}$ не изоморфен графовому ни для какого графа.# Сформулируйте и докажите аналогичный предыдущему заданию результат Когда двойственный к графовому матроид изоморфен графовому для некоторого графа?# Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $X = \{x_1, x_2, \alphaldots, 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 двух циклов обязательно содержит цикл. Доказать или опровергнуть.