Центр дерева

Под расстоянием d (a,b) между вершинами неориентированного графа, как и ранее, понимается минимальное число дуг в пути, соединяющем эти вершины.

ОПРЕДЕЛЕНИЕ 26. Эксцентриситетом вершины a неориентированного связного графа называется величина
, т.е. максимальное из расстояний от вершины a до всех вершин графа. Радиусом графа называется минимальный из эксцентриситетов вершин графа. Диаметром графа называется максимальный из эксцентриситетов вершин графа. Центром графа называется множество вершин, эксцентриситеты которых равны радиусу.

Центр дерева устроен очень просто.

Теорема 19. Центр дерева состоит либо из одной, либо из двух смежных вершин.

Доказательство. В деревьях, состоящих из одной или двух вершин эксцентриситеты вершин равны соответственно 0 или 1, т.е. центры таких графов совпадают с самими деревьями. Пусть в дереве не менее трех вершин. Удалим из дерева все листья. В результате получим дерево, эксцентриситеты всех вершин которого меньше, чем в исходном графе, на 1 (максимум расстояний от какой-нибудь вершины достигается на листьях). Отсюда, по определению центр полученного дерева совпадает с центом исходного. Повторяя эту процедуру, получим дерево, в котором либо одна, либо две вершины, что и требовалось.

Радиус дерева равен числу проведенных отсечений (если остается одна вершина), либо на 1 больше (если остается две вершины).