Изменения

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

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

2 байта убрано, 20:06, 12 октября 2020
опечатка
# Какое минимальное число вершин может быть в однозначно раскрашиваемом в 3 цвета графе, отличном от полного графа?
# Какое минимальное число ребер может быть в однозначно раскрашиваемом в $k$ цветов графе с $n$ вершинами?
# Доказать или опровернгнутьопровергнуть: любое вершинное покрытие содержит как подмножество минимальное по мощности вершинное покрытие.
# Доказать или опровергнуть: если в $G$ содержится реберно простой замкнутый путь, содержащий вершинное покрытие, то его реберный граф $E_G$ гамильтонов.
# Докажите, что $\alpha(G) \ge \frac{n}{1+\Delta(G)}$.
Анонимный участник

Навигация