Equitable partition

Материал из WEGA

Equitable partition --- справедливое разбиение.

Let [math]\displaystyle{ G }[/math] be a simple graph with a vertex set [math]\displaystyle{ V(G) }[/math]. A partition [math]\displaystyle{ \pi = (C_{1}, \ldots, C_{t}) }[/math] of [math]\displaystyle{ V(G) }[/math] is said to be equitable if, for all [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math], the number [math]\displaystyle{ c_{ij} }[/math] of edges from a vertex in [math]\displaystyle{ C_{i} }[/math] to [math]\displaystyle{ C_{j} }[/math] does not depend on the choice of the vertex in [math]\displaystyle{ C_{i} }[/math]. For an equitable partition [math]\displaystyle{ \pi }[/math], we denote the quotient graph with respect to [math]\displaystyle{ \pi }[/math] by [math]\displaystyle{ G/\pi }[/math]. The matrix [math]\displaystyle{ (c_{ij}) }[/math] is called the adjacency matrix of the quotient graph [math]\displaystyle{ G/\pi }[/math].