Clique-width: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Clique-width''' --- кликовая ширина. The '''clique-width''' of a graph <math>G</math>, denoted <math>cwd(G)</math>, is defined as a minimum number…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 17:14, 11 ноября 2013
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.