2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Задача на графы
Сообщение10.11.2014, 00:01 
Расстояния от двух соседних вершин дерева до любой фиксированной вершины отличаются на 1. Поэтому в дереве с чётным числом вершин удалённости любых двух соседних вершин отличаются на чётное число. Следовательно, удалённости всех вершин такого дерева имеют одинаковую чётность, и не могут отличаться на 1.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group