Аноним

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

Материал из WEGA
нет описания правки
(Новая страница: «'''Clique-width''' --- кликовая ширина. The '''clique-width''' of a graph <math>G</math>, denoted <math>cwd(G)</math>, is defined as a minimum number…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Clique-width''' --- кликовая ширина.  
'''Clique-width''' — ''[[кликовая ширина]].''


The '''clique-width''' of a graph <math>G</math>, denoted <math>cwd(G)</math>, is defined as
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.
a minimum number of labels needed to construct <math>G</math>, using four graph
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
operations: creation of a new vertex <math>v</math> with a label <math>i</math> (denoted <math>i(v)</math>),
consisted of two [[adjacent vertices]] <math>\,x</math> and <math>\,y</math> can be defined by
disjoint union of two 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 2 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
an expression <math>\eta_{1,2}(1(x) \oplus 2(y))</math>.
an expression <math>\eta_{1,2}(1(x) \oplus 2(y))</math>.


With any graph <math>G</math> and an algebraic expression <math>T</math> which defines <math>G</math> we
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.
associate a tree (denoted by <math>tree(T)</math>) whose leaves are the vertices of
 
<math>G</math>, and the internal 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
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.
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.