# Clique-width

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

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.