Задача
Расстоянием между двумя произвольными вершинами дерева будем называть длину простого пути, соединяющего их. Удалённостью вершины дерева назовём сумму расстояний от неё до всех остальных вершин. Докажите, что в дереве, у которого есть две вершины с удалённостями, отличающимися на 1, нечётное число вершин.
Решение
Соединим эти две вершины A и B путем. Пусть a – его длина. Расстояние от любой вершины до A и B отличаются на величину, имеющую ту же чётность, что и a. Поэтому если число вершин чётно, то (независимо от чётности a) удаленности A и B отличаются на чётное число, что противоречит условию.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет