4625
правок
Additive hereditary graph property: различия между версиями
Перейти к навигации
Перейти к поиску
Additive hereditary graph property (посмотреть исходный код)
Версия от 11:51, 7 ноября 2011
, 7 ноября 2011нет описания правки
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'''. | ||