Изменения
Нет описания правки
# Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$.
# Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$.
# Зафиксируем дерево $T$. Рассмотрим функцию от вершины $x$: $d(x) = \sum_v dist(x, v)$, где $dist(x, v)$ - расстояние между вершинами $x$ и $v$ в ребрах. Пусть $y$ и $z$ - различные соседи вершины $x$. Докажите, что $2d(x) < d(y) + d(z)$.
# Центром дерева называется вершина $x$, для которой $max_v(dist(x, v))$ минимален. Докажите, что у дерева 1 или 2 центра, и любой центр дерева лежит на его любом диаметре.
# Барицентром дерева называется вершина $x$, для которой $\sum_v(dist(x, v))$ минимальная. Докажите, что у дерева 1 или 2 барицентра.
# Докажите, что для любого $k$ существует дерево, для которого расстояние между центром и барицентром не меньше $k$.
# Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев.
# Обозначим как $\lambda(G)$ минимальное число ребер, которое нужно удалить в графе, чтобы он потерял связность, $\kappa(G)$ - минимальное число вершин, которое нужно удалить в графе, чтобы он потерял связность (для полного графа полагаем $\kappa(G)=n-1$). Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
# Докажите. что для любых $1 \le \kappa(G) \le \lambda(G) \le \delta(G)$ существует граф $G$ с такими параметрами.
# Докажите, что не существует графов с $\kappa(G) = 3$ и 7 ребрами.
# Пусть $G$ - полный двудольный граф, за исключением $K_{2,2}$. Докажите $\lambda(G)=\delta(G)$, почем единственный способ удалить $\lambda(G)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин.
