Деревья и остовные деревья
Ошибка.
Попробуйте повторить позже
В связном графе чётное число вершин. Докажите, что можно убрать из него часть рёбер так, что степень каждой вершины станет нечётной.
Подсказка 1.
Заметим, что если удалить ребро, сохраняющее связность, то утверждение задачи не изменится, а количество рёбер уменьшится. К чему в итоге приведёт такой процесс?
Выделим в графе остовное дерево Все рёбра графа, не входящие в
удалим. Теперь будем выбирать, какие рёбра остовного дерева
оставить, а какие — удалить. Подвесим дерево
за произвольную вершину
Будем определять судьбу рёбер, двигаясь от листьев к
корню, индукцией по высоте поддерева.
Для каждой вершины рассмотрим ребро
соединяющее
с её родителем. Решение о том, сохранять ли
будем принимать только тогда, когда уже приняты решения для всех рёбер, идущих из
к её детям, таким образом
степень вершины
не меняется после рассмотрения ребра
Пусть
— степень вершины
в текущем подграфе.
- Если
— нечётное число, то мы сохраняем ребро
Тогда степень
остается нечётной.
- Если
— четное число, то мы удаляем ребро
Степень
становится нечётной.
Таким образом, мы обеспечили нечётность степени для всех вершин графа, кроме, возможно, корня у которого нет родителя, и мы не
можем подкорректировать его степень ребром.
Проверим степень корня. Сумма степеней всех вершин в любом графе чётна (по лемме о рукопожатиях). Всего вершин кроме корня — нечетное число, и их степени также нечетны, то есть сумма степеней по всем вершнам кроме корня нечетна. Тогда и степень корня нечетна.
Специальные программы

Программа
лояльности вер. 2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к твоему аккаунту.

Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас важно быть полезными учителям по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

