English
!

Доклады

Центроидные вершины дерева

Белов Ю.А.

Россия, 150000, Ярославль, ул. Советская, 14, т. (4852) 458073, ЯрГУ им. П.Г. Демидова, кафедра теоретической информатики belov45@yandex.ru

Рассматривается дерево Т – связный граф без циклов. Порядок графа n(T) – количество его вершин. Как известно, количество рёбер при этом равно n-1=R(T), оно иногда называется размером. Для произвольной вершины v дерева можно рассмотреть набор поддеревьев, называемых ветвями данной вершины. Ветвь, при вершине v, есть максимальный подграф графа Т, для которого данная вершина является концевой. Количество ветвей, примыкающих к данной вершине v, равно степени этой вершины. Ветви, примыкающие к данной вершине v, не имеют общих рёбер и только одну общую вершину – вершину v, сумма размеров всех ветвей, примыкающих к произвольной вершине, равна размеру графа Т: n-1=R(T).

Определение. Для произвольной вершины v дерева T весом вершины называется максимум размеров ветвей, примыкающих к данной вершине v; будем обозначать его через w(v).

Например, если v – концевая вершина дерева, то к ней примыкает ровно одна ветвь, размер её равен n-1 и она просто совпадает со всем исходным графом. Таким образом, вес любой концевой вершины равен n-1. Вообще вес вершин, очевидно, находится в пределах от 1 до n-1.

Определение. Вершина называется центроидной, если её вес наименьший среди всех вершин дерева.

Получены следующие факты для центроидных вершин.

1. Вес любой центроидной вершины не превосходит n/2 и обратно, если вес некоторой вершины не превосходит n/2 , то она – центроидная.

2. Если в дереве имеется центроидная вершина v веса n/2, то имеется и другая центроидная вершина (естественно, того же веса), смежная с первой.

3. Если в дереве имеется более одной центроидной вершины, то порядок дерева чётный и вес любой центроидной вершины равен n/2 .

4. В любом дереве может быть только одна или две центроидные вершины. (следствие 1, 2, 3).

Однако, не всякое дерево чётного порядка является бицентрическим.

© 2004 Дизайн Лицея Информационных технологий №1533