Centroid: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''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>, …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 11:46, 7 ноября 2012
Centroid — центроид.
A branch of a tree [math]\displaystyle{ T }[/math] at a vertex [math]\displaystyle{ v }[/math] is a maximal subtree [math]\displaystyle{ T_{v} }[/math] of [math]\displaystyle{ T }[/math], in which the degree of [math]\displaystyle{ v }[/math] is unity. Therefore, the number of branches at [math]\displaystyle{ v }[/math] is [math]\displaystyle{ deg(v) }[/math]. The branch-weight centroid number of a vertex [math]\displaystyle{ v }[/math] in a tree [math]\displaystyle{ T }[/math], denoted by [math]\displaystyle{ bw(v) }[/math] is the the maximum size of any branch at [math]\displaystyle{ v }[/math]. A vertex [math]\displaystyle{ v }[/math] of a tree [math]\displaystyle{ T }[/math] is a centroid vertex of [math]\displaystyle{ T }[/math] if [math]\displaystyle{ v }[/math] has minimum branch-weight centroid number. The centroid of [math]\displaystyle{ T }[/math] consists of its set of centroid vertices. Jordan (1869) has proved the following theorem.
Theorem. The centroid of a tree consists of either a single vertex or a pair of adjacent vertices.
See also
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.