Изменения
Нет описания правки
# Вершинным покрытием называется множество вершин, такое что у каждого ребра хотя один конец лежит в этом множестве. Докажите, что $A$ является вершинным покрытием тогда и только тогда, когда $V\setminus A$ является независимым множеством.
# Доказать или опровернгнуть: любое вершинное покрытие содержит как подмножество минимальное по мощности вершинное покрытие.
# Доказать или опровергнуть: если в $G$ содержится реберно простой замкнутый путь, содержащий вершинное покрытие, то его реберный граф $E_G$ гамильтонов.
# Докажите, что $\alpha(G) \ge \frac{n}{1+\Delta(G)}$.
# Докажите, что $\alpha(G) \ge \sum (1 + \deg u)^{-1}$.
