Centroid

Материал из WikiGrapp
Версия от 16:11, 24 февраля 2011; 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>, …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

  • Slater number.