|
lexai |
|
|
|
Здравствуйте!
Помогите, пожалуйста, разобраться со следующей задачей: Расстоянием между двумя произвольными вершинами дерева будем называть длину простого пути, соединяющего их. Удаленностью вершины дерева назовем сумму расстояний от нее до всех остальных вершин. Докажите, что в дереве, у которого есть две вершины с удаленностями, отличающимися на 1, - нечетное число вершин.
|
|
|
|
 |
|
hippie |
|
|
|
Расстояния от двух соседних вершин дерева до любой фиксированной вершины отличаются на 1. Поэтому в дереве с чётным числом вершин удалённости любых двух соседних вершин отличаются на чётное число. Следовательно, удалённости всех вершин такого дерева имеют одинаковую чётность, и не могут отличаться на 1.
|
|
|
|
|
