Status of a vertex

Материал из WikiGrapp
Версия от 15:18, 28 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Status of a vertex''' --- статус вершины. The ''' status''' <math>s(v)</math> '''of a vertex''' <math>v</math> in <math>G</math> is the sum of the …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Status of a vertex --- статус вершины.

The status [math]\displaystyle{ s(v) }[/math] of a vertex [math]\displaystyle{ v }[/math] in [math]\displaystyle{ G }[/math] is the sum of the distances from [math]\displaystyle{ v }[/math] to all other vertices. Let [math]\displaystyle{ \chi (G) = r }[/math], so that [math]\displaystyle{ G }[/math] is [math]\displaystyle{ r }[/math]-chromatic. Let [math]\displaystyle{ S = \{v_{1}\lt v_{2}, \ldots, v_{r}\} }[/math] be a set of [math]\displaystyle{ r }[/math] vertices having distinct colors in a proper [math]\displaystyle{ r }[/math]-coloring of [math]\displaystyle{ G }[/math]. The total status of [math]\displaystyle{ S }[/math] is defined as the sum of distances

[math]\displaystyle{ \sum d(S) = \sum_{1 \leq i \lt  j \leq r} d(v_{i},v_{j}). }[/math] 

The Chromatic status [math]\displaystyle{ \sum \chi(G) }[/math] of [math]\displaystyle{ G }[/math] is the minimum value of the total status [math]\displaystyle{ \sum d(S) }[/math] of all sets [math]\displaystyle{ S }[/math] among all proper [math]\displaystyle{ r }[/math]-coloring of [math]\displaystyle{ G }[/math].