Изменения

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

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

150 байт добавлено, 18:56, 12 ноября 2018
Нет описания правки
# Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
# Докажите, что если $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
# Предложите алгоритм нахождения множества Татта в двудольном графе за $\mathcal{O}(nm)$.
Анонимный участник

Навигация