Изменения

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

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

16 байт добавлено, 22:50, 26 октября 2017
Нет описания правки
# Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$.
# Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$.
# Докажите, что для любого $1 \le k\le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ не превышает $n - k$.
# Графы $G_1$, содержащий $n_1$ вершин и $m_1$ ребер, и $G_2$, содержащий $n_2$ вершин и $m_2$ ребер, гомеоморфны. Докажите, что $n_1+m_2 = n_2+m_1$.
# Докажите, что планарный эйлеров граф содержит эйлеров цикл, не имеющий самопересечений.
Анонимный участник

Навигация