Differential of a graph

Материал из WikiGrapp
Версия от 13:23, 31 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Differential of a graph''' --- дифференциал графа. Let <math>B(X)</math> be the set of vertices in <math>V - X</math> that have a neighbor in t…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Differential of a graph --- дифференциал графа.

Let [math]\displaystyle{ B(X) }[/math] be the set of vertices in [math]\displaystyle{ V - X }[/math] that have a neighbor in the set [math]\displaystyle{ X }[/math]. We define the differential of a set [math]\displaystyle{ X }[/math] to be [math]\displaystyle{ \partial(X) = |B(X)| - |X| }[/math], and the differential of a graph to equal the [math]\displaystyle{ \max\{\partial(X)\} }[/math] for any subset [math]\displaystyle{ X }[/math] of [math]\displaystyle{ V }[/math].