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