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