244
правки
Изменения
Нет описания правки
# Найдите максимальное число ребер в графе с $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$ остовных деревьев.
# Дан код Прюфера дерева. Найдите степень каждой вершины, не восстанавливая дерево явно.
# Даны числа $d_1, d_2, \ldots, d_n$. Докажите, что количество деревьев, в которых $deg(1) = d_1$, ..., $deg(n) = d_n$ равно $\frac {(n-2)!} {\Pi (d_i - 1)!}$
# Обобщение формулы Кэли. Пусть дан полный граф, и остовный лес в нём, компоненты связности леса состоят из $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$,
# Обобщите матричную теорему Кирхгофа для следующей задачи: дан ориентированный граф и вершина $r$, нужно найти количество корневых деревьев с корнем в $r$.
