Differential of a graph

Материал из WEGA
Перейти к навигации Перейти к поиску

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].