Additive hereditary graph property: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Additive hereditary graph property''' --- аддитивное наследуемое свойство графа. An '''additive her...)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Additive hereditary graph property''' --- аддитивное наследуемое
'''Additive hereditary graph property''' — ''[[аддитивное наследуемое свойство графа]].''
свойство графа.  


An '''additive hereditary graph property''' is a set of graphs, closed
An '''additive hereditary graph property''' is a set of [[graph, undirected graph, nonoriented graph|graphs]], closed
under isomorphism and under taking subgraphs and ''disjoint unions''. Let
under isomorphism and under taking [[subgraph|subgraphs]] and ''disjoint unions''. Let
<math>{\mathcal P}_{1}, \ldots, {\mathcal P}_{n}</math> be additive hereditary graph
<math>{\mathcal P}_{1}, \ldots, {\mathcal P}_{n}</math> be additive hereditary graph
properties. A graph <math>G</math> has a property <math>({\mathcal P}_{1} \circ \cdots \circ
properties. A graph <math>\,G</math> has a property <math>({\mathcal P}_{1} \circ \cdots \circ
{\mathcal P}_{n})</math> if there is a partition <math>(V_{1}, \ldots, V_{n})</math> of
{\mathcal P}_{n})</math> if there is a partition <math>(V_{1}, \ldots, V_{n})</math> of
<math>V(G)</math> into <math>n</math> sets such that, for all <math>i</math>, the induced subgraph
<math>\,V(G)</math> into <math>,n</math> sets such that, for all <math>\,i</math>, the induced subgraph
<math>G[V_{i}]</math> is in <math>{\mathcal P}_{i}</math>. A property <math>{\mathcal P}</math> is '''reducible''' if there are properties <math>{\mathcal Q}</math> , <math>{\mathcal R}</math> such that
<math>\,G[V_{i}]</math> is in <math>{\mathcal P}_{i}</math>. A property <math>{\mathcal P}</math> is '''reducible''' if there are properties <math>{\mathcal Q}</math> , <math>{\mathcal R}</math> such that
<math>{\mathcal P} = {\mathcal Q} \circ {\mathcal R}</math>; otherwise it is '''irreducible'''.
<math>{\mathcal P} = {\mathcal Q} \circ {\mathcal R}</math>; otherwise it is '''irreducible'''.

Текущая версия от 11:51, 7 ноября 2011

Additive hereditary graph propertyаддитивное наследуемое свойство графа.

An additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let [math]\displaystyle{ {\mathcal P}_{1}, \ldots, {\mathcal P}_{n} }[/math] be additive hereditary graph properties. A graph [math]\displaystyle{ \,G }[/math] has a property [math]\displaystyle{ ({\mathcal P}_{1} \circ \cdots \circ {\mathcal P}_{n}) }[/math] if there is a partition [math]\displaystyle{ (V_{1}, \ldots, V_{n}) }[/math] of [math]\displaystyle{ \,V(G) }[/math] into [math]\displaystyle{ ,n }[/math] sets such that, for all [math]\displaystyle{ \,i }[/math], the induced subgraph [math]\displaystyle{ \,G[V_{i}] }[/math] is in [math]\displaystyle{ {\mathcal P}_{i} }[/math]. A property [math]\displaystyle{ {\mathcal P} }[/math] is reducible if there are properties [math]\displaystyle{ {\mathcal Q} }[/math] , [math]\displaystyle{ {\mathcal R} }[/math] such that [math]\displaystyle{ {\mathcal P} = {\mathcal Q} \circ {\mathcal R} }[/math]; otherwise it is irreducible.