Изменения
Нет описания правки
# Опишите все деревья с диаметром 2.
# Опишите все деревья с диаметром 3.
# Опишите дерево с кодом Прюфера $(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$.
# Обозначим как $\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)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин.
