Изменения

Перейти к: навигация, поиск

Список заданий по ДМ 2к 2020 осень

39 байт убрано, 23:06, 11 сентября 2020
Нет описания правки
# Докажите, что для любого $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}$.
Анонимный участник

Навигация