Centroid

Материал из WikiGrapp
Перейти к:навигация, поиск

Centroidцентроид.

A branch of a tree T at a vertex v is a maximal subtree T_{v} of T, in which the degree of v is unity. Therefore, the number of branches at v is deg(v). The branch-weight centroid number of a vertex v in a tree T, denoted by bw(v) is the the maximum size of any branch at v. A vertex v of a tree T is a centroid vertex of T if v has minimum branch-weight centroid number. The centroid of T 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.