Arbitrarily vertex decomposable graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Arbitrarily vertex decomposable graph''' --- произвольно вершинно разложимый граф. A graph <math>G</math> of order <math>n</mat…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Arbitrarily vertex decomposable graph''' | '''Arbitrarily vertex decomposable graph''' — ''[[произвольно вершинно разложимый граф]].'' | ||
вершинно разложимый граф. | |||
A graph <math>G</math> of order <math>n</math> is said to be '''arbitrarily vertex | A [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> of order <math>\,n</math> is said to be '''arbitrarily vertex decomposable''', if for each sequence <math>(n_{1}, \ldots, n_{k})</math> of positive integers such that <math>n_{1} + \ldots + n_{k} = n</math> there exists | ||
decomposable''', if for each sequence <math>(n_{1}, \ldots, n_{k})</math> of | a partition <math>(V_{1}, \ldots, V_{k})</math> of the [[vertex]] set of <math>\,G</math> such | ||
positive integers such that <math>n_{1} + \ldots + n_{k} = n</math> there exists | that, for each <math>i \in \{1, \ldots, k\}</math>, <math>V_{i}</math> induces a [[connected graph|connected]] [[subgraph]] of <math>\,G</math> on <math>\,n_{i}</math> vertices. | ||
a partition <math>(V_{1}, \ldots, V_{k})</math> of the vertex set of <math>G</math> such | |||
that, for each <math>i \in \{1, \ldots, k\}</math>, <math>V_{i}</math> induces a connected | |||
subgraph of <math>G</math> on <math>n_{i}</math> vertices. | |||
==See also== | ==See also== | ||
*''Admissible sequence''. | * ''[[Admissible sequence]]''. | ||
Текущая версия от 11:24, 5 декабря 2011
Arbitrarily vertex decomposable graph — произвольно вершинно разложимый граф.
A graph [math]\displaystyle{ \,G }[/math] of order [math]\displaystyle{ \,n }[/math] is said to be arbitrarily vertex decomposable, if for each sequence [math]\displaystyle{ (n_{1}, \ldots, n_{k}) }[/math] of positive integers such that [math]\displaystyle{ n_{1} + \ldots + n_{k} = n }[/math] there exists a partition [math]\displaystyle{ (V_{1}, \ldots, V_{k}) }[/math] of the vertex set of [math]\displaystyle{ \,G }[/math] such that, for each [math]\displaystyle{ i \in \{1, \ldots, k\} }[/math], [math]\displaystyle{ V_{i} }[/math] induces a connected subgraph of [math]\displaystyle{ \,G }[/math] on [math]\displaystyle{ \,n_{i} }[/math] vertices.