Admissible sequence: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Admissible sequence''' --- допустимая последовательность, Let <math>G = (V,E)</math> be a simple undirect...)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Admissible sequence''' --- допустимая последовательность,
'''Admissible sequence''' — ''[[допустимая последовательность]].''


Let <math>G = (V,E)</math> be a simple undirected graph of order <math>n</math>.
Let <math>\,G = (V,E)</math> be a simple [[graph, undirected graph, nonoriented graph|undirected graph]] of order <math>\,n</math>.
Let <math>\tau - (n_{1}, \ldots, n_{k})</math> denote a sequence of positive integers such
Let <math>\tau - (n_{1}, \ldots, n_{k})</math> denote a sequence of positive integers such
that <math>n_{1} + \ldots + n_{k} = n</math>. Such a sequence will be called '''admissible''' for <math>G</math>. If <math>\tau = (n_{1}, \ldots, n_{K})</math> is an
that <math>n_{1} + \ldots + n_{k} = n</math>. Such a sequence will be called '''admissible''' for <math>\,G</math>. If <math>\tau = (n_{1}, \ldots, n_{K})</math> is an
admissible sequence for <math>G</math> and there exists a partition <math>(V_{1},
admissible sequence for <math>\,G</math> and there exists a partition <math>(V_{1},
\ldots, V_{k})</math> of the vertex set <math>V</math> such that for each
\ldots, V_{k})</math> of the [[vertex]] set <math>\,V</math> such that for each
<math>i \in \{1, \ldots, k\}</math>, <math>|V_{i}| = n_{i}</math> and the subgraph induced by <math>V_{i}</math> is
<math>i \in \{1, \ldots, k\}</math>, <math>\,|V_{i}| = n_{i}</math> and the [[subgraph]] induced by <math>\,V_{i}</math> is
connected, then <math>\tau</math> is called '''realizable''' in <math>G</math> and the
connected, then <math>\,\tau</math> is called '''[[realizable admissible sequence|realizable]]''' in <math>\,G</math> and the
sequence <math>(V_{1}, \ldots, V_{k})</math> is said to be <math>G</math>-realization of
sequence <math>(V_{1}, \ldots, V_{k})</math> is said to be <math>\,G</math>-realization of
<math>\tau</math> or a realization of <math>\tau</math> in <math>G</math>. A graph <math>G</math> is '''arbitrarily vertex decomposable''' if for each admissible sequence
<math>\,\tau</math> or a realization of <math>\,\tau</math> in <math>\,G</math>. A graph <math>\,G</math> is '''arbitrarily vertex decomposable''' if for each admissible sequence
<math>\tau</math> for <math>G</math> there exists a <math>G</math>-realization of <math>\tau</math>.
<math>\,\tau</math> for <math>\,G</math> there exists a <math>\,G</math>-realization of <math>\,\tau</math>.

Навигация