|
Архив публикацийТезисыXXV-ая конференцияЦентроидные вершины дереваРоссия, 150000, Ярославль, ул. Советская, 14, т. (4852) 458073, ЯрГУ им. П.Г. Демидова, кафедра теоретической информатики belov45@yandex.ru 1 стр. (принято к публикации)Рассматривается дерево Т – связный граф без циклов. Порядок графа 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). Однако, не всякое дерево чётного порядка является бицентрическим. |
