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