Вопрос 35 из 42
Практика: доказательства и комбинаторные модели
Теорема Кёнига: паросочетание и покрытие всех рёбер
От чтения к действию
А теперь — вы
Разберёмся в теме
В конечном двудольном графе размер наибольшего паросочетания равен наименьшему числу вершин, касающихся всех рёбер. Такое множество вершин называется вершинным покрытием. По наибольшему паросочетанию покрытие строится через достижимость по чередующимся направлениям.
Частые вопросы
Где найти подробное решение?
Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.
Можно ли попробовать снова?
Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.