Просмотр исходного текста страницы Список заданий по ДМ 2к 2021 осень

# Во всех задачах этой серии графы неориентированные, ребро соединяет две различные вершины, между парой вершин есть не более одного ребра. Какое максимальное число ребер может быть в графе с $n$ вершинами?
# Какое максимальное число ребер может быть в графе с $n$ вершинами и двумя компонентами связности?
# Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее ""постройте граф с $n$ вершинами, ..."" означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
# Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Опишите все такие графы.
# Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$. Опишите все такие графы.
# Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
# Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
# Докажите, что в графе число вершин нечетной степени четно.
# Докажите, что если в графе ровно две вершины нечетной степени, то они лежат в одной компоненте связности.
# Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Для заданных $n$ и $k$ постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) = k$.
# Для заданных $n$, $d$ и $D$ постройте граф с $n$ вершинами, в котором $\delta(G) = d$, $\Delta(G) = D$.
# Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
# В графе $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ равны тогда и только тогда, когда в графе $G$ есть ребро $uv$. Что можно сказать про граф $G$?
# Граф называется кубическим, если степень всех вершин равна 3. Какое минимальное число вершин может быть в кубическом графе?
# Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
# Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это $R^*$.
# Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
# Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
# Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
# Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
# Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
# Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
# Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
# Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
# Докажите или опровергните, что в связном графе все простые пути, имеющие максимальную возможную длину в этом графе, имеют общую вершину.
# Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
# Приведите пример графа, что ни он, ни его дополнение не связаны путями длины не больше 2.
# Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем нечётных простых циклов.
# Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем чётных простых циклов.
# Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
# Центром графа называется вершина $u$, для которой кратчайшее расстояние до наиболее удаленной от $u$ вершины минимально. Докажите, что у дерева не более двух центров.
# Барицентром графа называется вершина $u$, сумма расстояний от которой до остальных вершин минимальна. Докажите, что у дерева не более двух барицентров.
# Каждое дерево является двудольным графом. А какие деревья являются полными двудольными графами?
# Докажите, что если $v$ точка сочленения в $G$, то $v$ не точка сочленения в $\overline G$.
# Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.
# Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?
# Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами?
# Диаметром графа называют максимальное значение кратчайшего пути между двумя его вершинами. Пусть связный граф $G$ имеет хотя бы 4 вершины и диаметр $d$. Докажите или опровергните, что у $G$ есть остовное дерево с диаметром $d$.
# Рассмотрим множество остовных деревьев связного графа $G$. Построим граф $S_G$, вершинами которого являются остовные деревья $G$, а две вершины $T_1$ и $T_2$ соединены ребром, если дерево $T_2$ можно получить из $T_1$ удалением одного ребра и добавлением другого. Докажите, что $S_G$ является связным.
# Докажите, что две вершины $T_1$ и $T_2$ в $S_G$ соединены ребром тогда и только тогда, когда их объединение содержит ровно один простой цикл.
# Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$. 
# Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$. 
# Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$.
# Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев.
# Обобщение формулы Кэли. Пусть дан полный граф из $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$,
# Дан код Прюфера дерева. Найдите степень каждой вершины, не восстанавливая дерево явно.
# Даны числа $d_1, d_2, \ldots, d_n$. Докажите, что количество деревьев, в которых $deg(1) = d_1$, ..., $deg(n) = d_n$ равно $\frac {(n-2)!} {\prod (d_i - 1)!}$
# Обобщите матричную теорему Кирхгофа для следующей задачи: дан ориентированный граф и вершина $r$, нужно найти количество корневых деревьев с корнем в $r$.