Изменения
Нет описания правки
# Постройте минимальный по числу вершин реберный граф, в котором нет гамильтонова цикла.
# Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий хотя бы одну вершину, инцидентную каждому ребру графа $G$.
# Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.# Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?# Докажите или опровергните, что если в связном графе любой максимальный по включению путь (путь, к которому нельзя добавить ребро в начало или в конец) является диаметром, то такой граф является деревом.# Опишите дерево с кодом Прюфера $(i, i,\ldots , i)$.# Опишите деревья, в коде Прюфера которых нет одинаковых чисел.# Зафиксируем дерево $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$ остовных деревьев.# Приведите пример графа с двумя непересекающимися остовными деревьями.# Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $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$. # Докажите, что для любого $k$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ не превышает $n - k$.
</wikitex>
