Clique-width: различия между версиями

'''Clique-width''' — ''[[кликовая ширина]].''

The '''clique-width''' of a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math>, denoted <math>\,cwd(G)</math>, is defined as a minimum number of [[label|labels]] needed to construct <math>\,G</math>, using four graph operations: creation of a new [[vertex]] <math>\,v</math> with a label <math>\,i</math> (denoted <math>\,i(v)</math>), disjoint union of two [[labeled graph, labelled graph|labeled graphs]] <math>\,G</math> and <math>\,H</math> (denoted <math>\,G \oplus H</math>), connecting vertices with specified labels <math>\,i</math> and <math>\,j</math> (denoted <math>\,\eta_{i,j}</math>) and renaming labels (denoted <math>\,\rho</math>). Every graph can be defined by an algebraic expression using the four operations above.

For instance, a graph consisted of <math>\,2</math> [[isolated vertex|isolated vertices]] <math>\,x</math> and <math>\,y</math> can be defined by an expression <math>\,1(x) \oplus 1(y)</math>, and a graph

consisted of two [[adjacent vertices]] <math>\,x</math> and <math>\,y</math> can be defined by

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

 

 

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