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