Additive hereditary graph property: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Additive hereditary graph property''' --- аддитивное наследуемое свойство графа. An '''additive her...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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.