Clique-width

Clique-width --- кликовая ширина.

The clique-width of a graph [math]\displaystyle{ G }[/math], denoted [math]\displaystyle{ cwd(G) }[/math], is defined as a minimum number of labels needed to construct [math]\displaystyle{ G }[/math], using four graph operations: creation of a new vertex [math]\displaystyle{ v }[/math] with a label [math]\displaystyle{ i }[/math] (denoted [math]\displaystyle{ i(v) }[/math]), disjoint union of two labeled graphs [math]\displaystyle{ G }[/math] and [math]\displaystyle{ H }[/math] (denoted [math]\displaystyle{ G \oplus H }[/math]), connecting vertices with specified labels [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] (denoted [math]\displaystyle{ \eta_{i,j} }[/math]) and renaming labels (denoted [math]\displaystyle{ \rho }[/math]). Every graph can be defined by an algebraic expression using the four operations above. For instance, a graph consisted of 2 isolated vertices [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] can be defined by an expression [math]\displaystyle{ 1(x) \oplus 1(y) }[/math], and a graph consisted of two adjacent vertices [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] can be defined by an expression [math]\displaystyle{ \eta_{1,2}(1(x) \oplus 2(y)) }[/math].

With any graph [math]\displaystyle{ G }[/math] and an algebraic expression [math]\displaystyle{ T }[/math] which defines [math]\displaystyle{ G }[/math] we associate a tree (denoted by [math]\displaystyle{ tree(T) }[/math]) whose leaves are the vertices of [math]\displaystyle{ G }[/math], and the internal nodes correspond to operations [math]\displaystyle{ \oplus }[/math], [math]\displaystyle{ \eta }[/math] and [math]\displaystyle{ \rho }[/math] in [math]\displaystyle{ T }[/math]. Given a node [math]\displaystyle{ a }[/math] in [math]\displaystyle{ tree(T) }[/math], we denoted by [math]\displaystyle{ tree(a,T) }[/math] the subtree of [math]\displaystyle{ tree(T) }[/math] rooted at [math]\displaystyle{ a }[/math]. The label of a vertex [math]\displaystyle{ v }[/math] of [math]\displaystyle{ G }[/math] at the node [math]\displaystyle{ a }[/math] of [math]\displaystyle{ tree(T) }[/math] is defined as the label that [math]\displaystyle{ v }[/math] has immediately before the operation [math]\displaystyle{ a }[/math] is applied.