Clique-width

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

Литература

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