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.

Текущая версия от 10:47, 24 октября 2018

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.