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 [math]\displaystyle{ \,2 }[/math] 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.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.