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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''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>.

Текущая версия от 15:15, 17 ноября 2011

Admissible sequenceдопустимая последовательность.

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