Centroid: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Centroid''' --- центроид. A '''branch''' of a tree <math>T</math> at a vertex <math>v</math> is a maximal subtree <math>T_{v}</math> of <math>T</math>, …»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Centroid''' --- центроид.  
'''Centroid''' — [[центроид]].  


A '''branch''' of a tree <math>T</math> at a vertex <math>v</math> is a maximal subtree
A '''branch''' of a [[tree]] <math>T</math> at a [[vertex]] <math>v</math> is a maximal [[subtree]]
<math>T_{v}</math> of <math>T</math>, in which the degree of <math>v</math> is unity. Therefore, the number of branches at <math>v</math> is <math>deg(v)</math>. The '''branch-weight centroid number''' of a vertex <math>v</math> in a tree <math>T</math>, denoted by <math>bw(v)</math> is the
<math>T_{v}</math> of <math>T</math>, in which the [[degree of a vertex|degree]] of <math>v</math> is unity. Therefore, the number of branches at <math>v</math> is <math>deg(v)</math>. The '''[[branch-weight centroid number]]''' of a vertex <math>v</math> in a tree <math>T</math>, denoted by <math>bw(v)</math> is the
the maximum size of any branch at <math>v</math>. A vertex <math>v</math> of a tree <math>T</math> is a '''centroid vertex''' of <math>T</math> if <math>v</math> has minimum branch-weight centroid
the maximum size of any branch at <math>v</math>. A vertex <math>v</math> of a tree <math>T</math> is a '''[[centroid vertex]]''' of <math>T</math> if <math>v</math> has minimum branch-weight centroid
number. The '''centroid''' of <math>T</math> consists of its set of centroid vertices.
number. The '''centroid''' of <math>T</math> consists of its set of centroid vertices.
Jordan (1869) has proved the following theorem.
Jordan (1869) has proved the following theorem.


'''Theorem.''' The centroid of a tree consists of either a single
'''Theorem.''' The centroid of a tree consists of either a single
vertex or a pair of adjacent vertices.
vertex or a pair of [[adjacent vertices]].
==See also==
==See also==
*''Slater number''.
* ''[[Slater number]]''.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Навигация