Изменения

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

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

85 байт добавлено, 16:55, 7 сентября 2019
Нет описания правки
# Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
# Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем нечётных простых циклов.
# Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем чётных простых циклов.
# Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
# Доказать или опровергнутьДокажите, что если ребро $uv$ - наименьшее число вершин в кубическом графе, в котором есть мост, то $u$ и $v$ - точки сочлененияравно 10.# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.# Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
Анонимный участник

Навигация