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