Изменения
Нет описания правки
# Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
# Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
# Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это $R^*$.
# Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
# Каждое дерево является двудольным графом. А какие деревья являются полными двудольными графами?
# Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
# Докажите, что если $v$ точка сочленения в $G$, то $v$ не точка сочленения в $\overline G$.
# Опишите дерево с кодом Прюфера $(i, i,\ldots , i)$.
# Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.
# Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?
# Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами?
# Диаметром графа называют максимальное значение кратчайшего пути между двумя его вершинами. Пусть связный граф $G$ имеет диаметр $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_1c_2\ldots c_n(c_1+c_2+\ldots+c_n)^{n-2}$.
