3.05.3. Типы вершин дерева, радиус и центры

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

Теорема. Существует не более двух центров дерева. Они совпадают с вершинами максимального типа. Радиус дерева R(G) равен , если центр единственный и его тип , или , если центра два и их тип .

< Предыдущая		Следующая >