Удаление ребра из дерева — задача по олимпиадной математике
Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.
Разобрать решение
Предположим, что концы удалённого ребра в новом графе соединены простым путем. Тогда этот путь вместе с удалённым ребром образует в исходном графе цикл.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.